构造完全图

题目描述:

对于完全图G， 若有且仅有一棵最小生成树T，则称完全图G是树T扩展出的。

给你一棵树T，找到T能扩展出的边权和最小的完全图G。

 

输入格式:

第一行N表示树T的点数。

接下来N-1行： Si, Ti, Di描述一条边( Si , Ti )权值为Di 。

保证输入数据构成一棵树。

输出格式:

输出仅一个数，表示最小的完全图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<=100，000， 1<= Di <=100,000。

时间限制: 1000ms
空间限制: 256MB

---