构造完全图

【题目描述】

对于完全图$G$,若有且仅有一棵最小生成树为$T$，则称完全图G是树T的扩展出的。给你一棵树T,找出T能扩展出的边权和最小的完全图$G$。

【输入】

第一行$N$表示树$T$的点数。 接下来$N-1$行：$S_i，T_i，D_i$；描述一条边（$S_i,T_i$）权值为 $D_i$。 保证输入数据构成一棵树。

【输出】

一个数，表示最小的图$G$的边权和。

【输入样例】

4
1 2 1
1 3 1
1 4 2

【输出样例】

12

【提示】

【样例说明】 添加$D(2,3)=2,D(3,4)=3,D(2,4)=3$即可。 【数据规模】 对于20%的数据，$N<=10$ 对于50%的数据，$N<=1000$ 对于100%的数据，$N<=100000，1<=D_i<=100000$