2575: 构造完全图
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
对于完全图 $G$，若有且仅有一棵最小生成树为 $T$，则称完全图 $G$ 是树 $T$ 扩展出的。
给你一棵树 $T$，找出 $T$ 能扩展出的边权和最小的完全图 $G$。
给你一棵树 $T$，找出 $T$ 能扩展出的边权和最小的完全图 $G$。
输入
第一行 $N$ 表示树 $T$ 的点数；
接下来 $N−1$ 行三个整数 $S_i, T_i, D_i$ ；描述一条边（$S_i, T_i$）权值为 $D_i$ ；
保证输入数据构成一棵树。
接下来 $N−1$ 行三个整数 $S_i, T_i, D_i$ ；描述一条边（$S_i, T_i$）权值为 $D_i$ ；
保证输入数据构成一棵树。
输出
输出仅一个数，表示最小的完全图 $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≤10^5,1≤D_i≤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≤D_i≤10^5$ 。