3677: 绵羊的反击
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：1
题目描述
HXY给绵羊出了一道题目：给定一张完全图，求它的最小生成树。
这样的题目怎么可能难住绵羊？于是绵羊反击了！
绵羊给出了一张完全图的唯一最小生成树。
现在问完全图中所有边可能的最小边权和是多少。
Ps:完全图是任意两个点之间都有边相连的图。
输入
第一行包含一个整数T表示数据组数。
每组数据第一行一个整数N表示点数。
接下来N-1行每行三个整数ai，bi，wi，表示最小生成树上ai和bi之间有一条权值为wi的边。
输出
输出有T行，每行表示一组数据的答案。
样例输入 复制
2
3
1 2 4
2 3 7
4
1 2 1
1 3 1
1 4 2
样例输出 复制
19
12
提示
20%的数据满足：T≤5，n≤5，wi≤5；
另外30%的数据满足：n≤1000，且给定的树是一条链；
100%的数据满足：T≤10，n≤20000，wi≤10000。