Problem Description

Given a tree with $N$ nodes, you need to add some edges to extend this tree into a complete graph, while ensuring that the unique minimum spanning tree of the graph is still this tree.

Find the minimum possible total weight of the added edges.

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

Input Format

The first line contains an integer $t$, meaning there are $t$ groups of testdata.

For each group of testdata, the first line contains an integer $N$.

The next $N-1$ lines each contain three integers $X, Y, Z$, meaning there is an edge between node $X$ and node $Y$ with length $Z$.

Output Format

For each group of testdata, output one integer, meaning the minimum total weight.

Each result occupies one line.

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

4
17

Hint

Constraints: $1 \le t \le 10$, $1 \le N \le 6000$, $1 \le Z \le 100$.

Translated by ChatGPT 5