题目描述
小明给出了一张完全图的唯一最小生成树。现在问完全图中所有边可能的最小边权和是多少。
输入
第一行包含一个整数 $T$ 表示数据组数。
每组数据第一行一个整数 $N$ 表示点数。
接下来 $N-1$ 行每行三个整数 $a_i,b_i,w_i$，表示最小生成树上 $a_i$ 和 $b_i$ 之间有一条权值为 $w_i$ 的边。
输出
输出有 $T$ 行，每行表示一组数据的答案。
样例输入输出
输入#1
复制
2
3
1 2 4
2 3 7
4
1 2 1
1 3 1
1 4 2
提示
对于 $20\%$ 的数据，$T \leq 5$，$n \leq 5$，$w_i \leq 5$；
对于另外 $30\%$ 的数据：$n \leq 10^3$，且给定的树是一条链；
对于 $100\%$ 的数据: $T \leq 10$，$1 \leq n \leq 2 \times 10^4$，$1 \leq w_i \leq 10^4$。