2769: 「一本通 3.1 练习 2」构造完全图
Memory Limit：512 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：8
Solved：5
Description
对于完全图 GGG，若有且仅有一棵最小生成树为 TTT，则称完全图 GGG 是树 TTT 扩展出的。
给你一棵树 TTT，找出 TTT 能扩展出的边权和最小的完全图 GGG。
Input
第一行 NNN 表示树 TTT 的点数；
接下来 N−1N-1N−1 行三个整数 Si,Ti,DiS_i, T_i, D_iSi,Ti,Di；描述一条边（Si,TiS_i, T_iSi,Ti）权值为 DiD_iDi；
保证输入数据构成一棵树。
Output
输出仅一个数，表示最小的完全图 GGG 的边权和。
HINT
样例输入
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)=3D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。
对于 20%20\%20% 的数据，N≤10Nle 10N≤10；
对于 50%50\%50% 的数据，N≤1000Nle 1000N≤1000；
对于 100%100\%100% 的数据，N≤105,1≤Di≤105Nle 10^5, 1le D_ile 10^5N≤105,1≤Di≤105。