Minimum Total Weight to Form a Complete Graph with Unique MST

Given a tree with N nodes, we need to add several edges to expand it into a complete graph, while ensuring that the unique minimum spanning tree of the resulting graph remains the original tree.

Find the minimum total weight of the added edges.

Note: All edge weights in the original tree are integers, and all newly added edge weights must also be integers.

Input Format
The first line contains an integer t, indicating the number of test cases.

For each test case:
The first line contains an integer N.
The next N-1 lines each contain three integers X, Y, Z, indicating that there is an edge between node X and node Y with length Z.

Output Format
For each test case, output a single integer representing the minimum total weight of the added edges. Each result should be on a separate line.

Constraints
1 ≤ N ≤ 6000
1 ≤ Z ≤ 100

Sample Input

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

Sample Output

4
17