不能和其他题目重名的最小生成树

题目

知识点：最小生成树的Kruskal 算法

已知一个完全图唯一的最小生成树（即知道这个树所有边的端点和权值）,其余的边权值未知，问这个完全图所有边权值和的最小值。

完全图是每对顶点之间都恰连有一条边的简单图。

输入

第一行一个整数t表示数据组数($1\le t \le 10$)

每组数据第一行一个正整数n，表示完全图的点数($2\le n\le 10^5$)

接下来n-1行，每行三个整数x，y，z，表示x,y之间有一条权值为z的边（无向边） ($1\le x,y\le n，1\le z \le 10000$)

输出

每组数据一行一个整数

输入样例

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

输出样例

9
29