Chandu is a problem setter at HackerEarth. He used to call all his seniors, Gurudev. Once Gurudevs realized Chandu is getting lazy, and they asked to him to set a problem. So he came up with a problem. He explained the problem to Gurudevs.

Given a undirected graph G with N nodes. The graph G has 2 properties:

G is connected
G has N-1 edges

Then he defined a function F such that F(a, b) is equal to the maximum edge weight in the path from a to b.

Now the problem is quite simple. We need to find the sum of the F(a, b) for all a, b such that 1 <= a, b <= N (mod 10⁹ + 7).

As we all know that Chandu is lazy. Chandu submitted the problem but he did not submit the solution of the problem. So he asked you to write the solution for him.

Input:
First line contains an integer T, number of test cases.
First line of each test case consists of an integer N, number of nodes.
Next N-1 lines follows. i^th line contains three space separated integers a_i, b_i and c_i which denotes that there is an edge from a_i to b_i with edge weight c_i.

Output:
For each test case print a single integer that is equal to the sum of the F(a, b) for all a, b such that 1 <= a, b <= N (mod 10⁹ + 7).

Constraints:
1 <= T <= 10⁵
1 <= N <= 2 * 10⁵
0 <= c_i <= 10⁸
1 <= a_i, b_i <= N
sum of N over all the testcases will be <= 2 * 10⁶