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

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

题目描述

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

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

输入格式

第一行 N 表示树 T 的点数;

接下来 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\le 10
对于 50\% 的数据, N\le 1000
对于 100\% 的数据, N\le 10^5, 1\le D_i\le 10^5