ドワーフたちは新しい地下の村を建設したばかりです。今こそ、村の中で運行する鉄道網を計画する時です。

村は $N$ 個の交差点と、それらを結ぶ $N - 1$ 本のトンネルからなります。トンネルは、どの交差点から他のどの交差点へも到達できるように建設されています。行き止まりになっている（つまり、$1$ 本のトンネルだけで接続されている）各交差点には、鉄道の駅があります。

あなたの課題は、村を走る列車の路線を決定することです。ドワーフたちの要求を満たすため、すべての駅をペアにする必要があり（幸いなことに、駅の数は偶数です）、各ペアの間には最短経路を通る列車が $1$ 本ずつ運行されます。ただし、トンネルには制限があります。各トンネルの長さは同じ（$1$ に等しい）ですが、その幅により通過できる路線の数には上限があります。

ドワーフたちは、列車の路線の総延長をできるだけ長くしたいと考えています。最大の総延長がいくつになるか計算できますか？

入力

入力の $1$ 行目には、村の交差点の数を表す $1$ つの整数 $N$ が含まれます。

続く $N - 1$ 行のそれぞれには、$3$ つの整数 $a_i$, $b_i$, $c_i$ が含まれ、交差点 $a_i$ と $b_i$ の間にトンネルがあることを表します。値 $c_i$ は、このトンネルを通過できる路線の数の上限です。

出力

$1$ 行目（唯一の行）に、選ばれた駅のペア間の経路の最大総延長を表す整数を $1$ つ出力してください。

制約を満たしながら駅をペアにする方法が存在しない場合は、$-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