矮人們剛剛建好了他們新的地下村莊。現在是時候規劃在其中運行的鐵路網了。

村莊由 $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