Dvärgarna har precis byggt sin nya underjordiska by. Nu är det dags att planera järnvägsnätet som ska drivas inom den.

Byn består av $N$ korsningar och $N - 1$ tunnlar som förbinder dem. Tunnlarna har byggts på ett sådant sätt att det är möjligt att nå vilken korsning som helst från vilken annan som helst. Vid varje korsning som är en återvändsgränd (vilket innebär att den endast är ansluten med en tunnel) finns det en tågstation.

Din uppgift är att bestämma rutterna för tågen i byn. För att uppfylla dvärgarnas krav måste alla stationer paras ihop (lyckligtvis finns det ett jämnt antal av dem), och det kommer att gå ett tåg mellan varje par som använder den kortast möjliga vägen. Tunnlarna har dock sina begränsningar. Även om varje tunnel har samma längd (lika med $1$), tillåter deras bredd endast ett begränsat antal rutter att passera igenom.

Dvärgarna vill att den totala längden på tågrutterna ska vara så lång som möjligt. Kan du beräkna vad den maximala längden kan bli?

Indata

Den första raden i indatan innehåller ett heltal $N$, som representerar antalet korsningar i byn.

Var och en av de följande $N - 1$ raderna innehåller tre heltal $a_i$, $b_i$, $c_i$, som representerar en tunnel mellan korsningarna $a_i$ och $b_i$. Värdet $c_i$ är en övre gräns för antalet rutter som kan passera genom denna tunnel.

Utdata

På den första och enda raden ska du skriva ut ett enda heltal som representerar den maximala totala längden på vägarna mellan de valda paren av stationer.

Om det inte finns något sätt att para ihop stationerna samtidigt som villkoren uppfylls, skriv ut $-1$.

Begränsningar

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, alla korsningar är sammanbundna, och antalet stationer (dvs. återvändsgränder) är jämnt.

Exempel

Indata 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

Utdata 1

10

Förklaring

I det första exemplet ger en anslutning av stationerna vid korsningarna $5\text{--}9$, $6\text{--}7$ och $8\text{--}10$ en total längd på tågrutterna som är lika med $4 + 3 + 3 = 10$.

Indata 2

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

Utdata 2

-1