6567 - 构造完全图
时间限制 : 1 秒
内存限制 : 128 MB
对于完全图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≤100000,1≤Di≤100000。
来源
一本通