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

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

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

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

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


Input

第一行 NNN 表示树 TTT 的点数;

接下来 N−1N-1N1 行三个整数 Si,Ti,DiS_i, T_i, D_iSi,Ti,Di;描述一条边(Si,TiS_i, T_iSi,Ti)权值为 DiD_iDi

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


Output

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


Sample Input

4  
1 2 1  
1 3 1  
1 4 2

Sample Output

12

HINT

对于 20%20\%20% 的数据,N≤10N\le 10N10
对于 50%50\%50% 的数据,N≤1000N\le 1000N1000
对于 100%100\%100% 的数据,N≤105,1≤Di≤105N\le 10^5, 1\le D_i\le 10^5N105,1Di105


Source/Category


Submit Status