2289: 【信息学奥赛一本通】构造完全图
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：5
Solved：5
Description
对于完全图 G，若有且仅有一棵最小生成树为 T，则称完全图 G 是树 T 扩展出的。
给你一棵树 T，找出 T 能扩展出的边权和最小的完全图 G。
给你一棵树 T，找出 T 能扩展出的边权和最小的完全图 G。
Input
第一行 N 表示树 T 的点数；
接下来 N−1 行三个整数 Si,Ti,Di ；描述一条边（Si,Ti）权值为 Di ；
保证输入数据构成一棵树。
接下来 N−1 行三个整数 Si,Ti,Di ；描述一条边（Si,Ti）权值为 Di ；
保证输入数据构成一棵树。
Output
输出仅一个数，表示最小的完全图 G 的边权和。
Sample Input Copy
4
1 2 1
1 3 1
1 4 2Sample Output Copy
12HINT
样例说明
添加 D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。
数据范围：
对于 20% 的数据，N≤10；
对于 50% 的数据，N≤1000；
对于 100% 的数据，N≤10^5,1≤Di≤10^5 。
添加 D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。
数据范围：
对于 20% 的数据，N≤10；
对于 50% 的数据，N≤1000；
对于 100% 的数据，N≤10^5,1≤Di≤10^5 。