In 9102, HRY was elected as the director of the GDCPC Metro Bureau. In his work, he needs to use his knowledge to solve some problems.
The subway line of GDCPC can be regarded as a connected graph composed of n points and n-1 edges. The edge weight represents the distance between two points. The weight of the path between two different points is defined as the maximum value of the edge weights of all edges on the simple path between them. Now HRY needs to know the sum of the weights of all pairs of points (obviously there are kinds), because he is busy, so he wants you, a JBer, to helped him calculate it.

The first line of the input file contains a positive integer T, indicating the number of test cases.
Each case has n lines. The first line is a positive integer n, indicating the number of points; the next n-1 lines each line contains three positive integers u, v, w, indicating that there is an edge between u and v, and the weight of this edge is w.
It is guaranteed that the input forms a tree.

The sum of n does not exceed 2000000.

For each test case, output a line of a positive integer representing the sum of the weights of all paths.

2
3
1 2 1
2 3 2
4
1 2 1
1 3 2
1 4 3

5
14