题目描述
对于完全图
G
G，若有且仅有一棵最小生成树为
T
T，则称完全图
G
G 是树
T
T 扩展出的。
给你一棵树
T
T，找出
T
T 能扩展出的边权和最小的完全图
G
G。
输入
第一行
N
N 表示树
T
T 的点数；
接下来
N-1
N−1 行三个整数
S_i, T_i, D_i
Si
,Ti
,Di
；描述一条边（
S_i, T_i
Si
,Ti
）权值为
D_i
Di
；
保证输入数据构成一棵树。
输出
输出仅一个数，表示最小的完全图
G
G 的边权和。
样例输入
4
1 2 1
1 3 1
1 4 2
样例输出
12
提示
样例说明
添加
D(2, 3)=2, D(3, 4)=3, D(2, 4)=3
D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。
数据范围与提示
对于
20\%
20% 的数据，
N\le 10
N≤10；
对于
50\%
50% 的数据，
N\le 1000
N≤1000；
对于
100\%
100% 的数据，
N\le 10^5, 1\le D_i\le 10^5
N≤105,1≤Di
≤105。
来源/分类
ybttg 最小生成树