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

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

题目描述

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

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

输入

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

接下来 N1N−1 行三个整数 S_i,T_i,D_iS\_i, T\_i, D\_i​​​​ ;描述一条边(S_i,T_iS\_i, T\_i)权值为 D_iD\_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% 的数据,N10N≤10

对于 50% 的数据,N1000N≤1000

对于 100% 的数据,N105,1D_i105N≤10^5,1≤D\_i≤10^5​ 。

来源

一本通在线评测