You are given a Tree of n nodes numbered from 1 to n.

Let us take two nodes say c and d. Then, the lazy value of a path between (c, d) is equal to the maximum of all edges on that path.

You need to find the sum of all lazy values for all pairs of nodes.

Here, we define any pair of node as (c, d) where 1 <= c, d <= n.

As sum can be very large, output it modulo ((10^9) + 7).

Use of Fast I/O is recommended.

Input format:

First line contains T number of testcases.

Each test case is as per the following format:

First line consists of an integer n, denoting number of nodes.

Next n - 1 lines follows.

Each line contains three space-separated integers a, b and c, which denotes that there is an edge from a to b with edge weight c.

Output format:

Output the required answer

Constraints:

1 <= T <= 10^5

1 <= N <= 2 * 10^5

0 <= c <= 10^9

1 <= a, b <= N

Note: sum of n over all the testcases will be <= 2 * 10^6