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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

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

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

输入格式

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

接下来 N1N-1 行三个整数 Si,Ti,DiS_i, T_i, D_i;描述一条边(Si,TiS_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