#157. 「一本通 3.1 练习 2」构造完全图

「一本通 3.1 练习 2」构造完全图

题目描述

对于完全图 GG,若有且仅有一棵最小生成树为 TT,则称完全图 GG 是树 TT 扩展出的。

给你一棵树 TT,找出 TT 能扩展出的边权和最小的完全图 GG

输入格式

第一行 NN 表示树 TT 的点数;

接下来 N1N-1 行三个整数 Si,Ti,DiS_i, T_i, D_i;描述一条边 (Si,Ti)(S_i, T_i) 权值为 DiD_i

保证输入数据构成一棵树。

输出格式

输出仅一个数,表示最小的完全图 GG 的边权和。

样例

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%20\% 的数据,N10N\le 10
对于 50%50\% 的数据,N1000N\le 1000
对于 100%100\% 的数据,N105,1Di105N\le 10^5, 1\le D_i\le 10^5