對(duì)于完全圖 G，若有且僅有一棵最小生成樹(shù)為 T，則稱完全圖 G 是樹(shù) T 擴(kuò)展出的。

給你一棵樹(shù) T，找出 T 能擴(kuò)展出的邊權(quán)和最小的完全圖 G。

第一行 N 表示樹(shù) T 的點(diǎn)數(shù)；

接下來(lái) N?1 行三個(gè)整數(shù) S_i,T_i,D_i ；描述一條邊（S_i,T_i）權(quán)值為 D_i ；

保證輸入數(shù)據(jù)構(gòu)成一棵樹(shù)。

4  
1 2 1  
1 3 1  
1 4 2

12

樣例說(shuō)明

添加 D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。

數(shù)據(jù)范圍：

對(duì)于 20% 的數(shù)據(jù)，N≤10；

對(duì)于 50% 的數(shù)據(jù)，N≤1000；

對(duì)于 100% 的數(shù)據(jù)，N≤10⁵,1≤D_i≤10⁵ 。