Source : 一本通提高篇
Description
对于完全图G,若有且仅有一棵最小生成树为T,则称完全图G是树T的扩展出的。给你一 棵树T,找出T能扩展出的边权和最小的完全图G。
Input
第一行N表示树T的点数。 接下来N-1行:Si,Ti,Di;描述一条边(Si,Ti)权值为 Di。 保证输入数据构成一棵树。
Output
一个数,表示最小的图G的边权和。
Sample Input
4
1 2 1
1 3 1
1 4 2
Sample Output
12
Hint
 对于20%的数据,N<=10 对于50%的数据,N<=1000 对于100%的数据,N<=100000,1<=Di<=100000