矮人們啱啱起好咗佢哋嘅新地下村莊。而家係時候規劃喺入面運行嘅鐵路網絡喇。

村莊由 $N$ 個交叉路口同連接佢哋嘅 $N - 1$ 條隧道組成。隧道嘅建造方式保證咗可以由任何一個交叉路口去到其他任何一個交叉路口。喺每一個掘頭路（即係淨係得一條隧道連接嘅交叉路口）嗰度，都有一個火車站。

你嘅任務係決定村莊入面火車嘅路線。為咗滿足矮人們嘅要求，所有火車站必須兩兩配對（好彩火車站嘅數量係偶數），而且每一對火車站之間都會有一列火車運行，行駛佢哋之間最短嘅路徑。不過，隧道都有佢哋嘅限制。雖然每條隧道嘅長度都一樣（等於 $1$），但佢哋嘅闊度只係容許有限數量嘅路線通過。

矮人們希望火車路線嘅總長度越長越好。你能唔能夠計出最大可能嘅總長度係幾多？

輸入格式

輸入嘅第一行包含一個整數 $N$，代表村莊入面交叉路口嘅數量。

接落嚟嘅 $N - 1$ 行，每行包含三個整數 $a_i$、$b_i$、$c_i$，代表交叉路口 $a_i$ 同 $b_i$ 之間有一條隧道。數值 $c_i$ 係可以通過呢條隧道嘅路線數量上限。

輸出格式

喺第一行亦即係唯一一行入面，輸出一個整數，代表所選火車站配對之間路徑嘅最大總長度。

如果冇辦法喺滿足限制條件嘅情況下將所有火車站配對，請輸出 $-1$。

數據範圍

$2 \le N \le 200\,000$，$1 \le a_i, b_i \le N$，$0 \le c_i \le N$，所有交叉路口都係連通嘅，而且火車站（即掘頭路）嘅數量係偶數。

樣例

輸入格式 1

10
1 2 2
2 3 1
3 4 3
5 1 1
6 1 2
7 2 3
8 3 2
9 3 1
10 4 7

輸出格式 1

10

說明

喺第一個樣例入面，連接位於交叉路口 $5\text{--}9$、$6\text{--}7$ 同 $8\text{--}10$ 嘅火車站，可以得到總長度等於 $4 + 3 + 3 = 10$ 嘅火車路線。

輸入格式 2

5
1 2 3
1 3 1
1 4 0
1 5 2

輸出格式 2

-1