算苗
在算苗科技,
享受AC的欢乐
对于完全图GG，若有且仅有一棵最小生成树为TT，则称完全图GG 是树TT 扩展出的。
给你一棵树TT，找出TT 能扩展出的边权和最小的完全图GG。
第一行NN 表示树TT 的点数；
接下来N−1N−1 行三个整数Si,Ti,DiSi,Ti,Di ；描述一条边（Si,TiSi,Ti）权值为DiDi ；
保证输入数据构成一棵树。
4 1 2 1 1 3 1 1 4 2
12
样例说明
添加D(2,3)=2,D(3,4)=3,D(2,4)=3D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。
数据范围：
对于 20% 的数据，N≤10N≤10；
对于 50% 的数据，N≤1000N≤1000；
对于 100% 的数据，N≤105,1≤Di≤105。