P10928 Corridor Water-Splashing Festival

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.

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$.

For each group of testdata, output one integer, meaning the minimum total weight. Each result occupies one line.

Constraints: $1 \le t \le 10$, $1 \le N \le 6000$, $1 \le Z \le 100$. Translated by ChatGPT 5