Dvergarnir eru nýbúnir að byggja nýja neðanjarðarþorpið sitt. Nú er kominn tími til að skipuleggja járnbrautarnetið sem mun starfa innan þess.

Þorpið samanstendur af $N$ gatnamótum og $N - 1$ göngum sem tengja þau saman. Göngin hafa verið byggð þannig að hægt er að komast á hvaða gatnamót sem er frá hvaða öðrum gatnamótum sem er. Á hverjum gatnamótum sem eru botnlangi (sem þýðir að þau eru aðeins tengd með einum göngum) er lestarstöð.

Verkefni þitt er að ákvarða leiðirnar fyrir lestirnar í þorpinu. Til að uppfylla kröfur dverganna verður að para saman allar stöðvar (sem betur fer er sléttur fjöldi af þeim), og ein lest mun ganga á milli hvers pars eftir stystu mögulegu leið. Göngin hafa þó sínar takmarkanir. Þótt öll göngin séu jafnlöng (jöfn $1$), leyfir breidd þeirra aðeins takmörkuðum fjölda leiða að liggja í gegnum þau.

Dvergarnir vilja að heildarlengd lestarleiðanna sé eins mikil og mögulegt er. Geturðu reiknað út hver hámarkslengdin getur orðið?

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $N$, sem táknar fjölda gatnamóta í þorpinu.

Hver af næstu $N - 1$ línum inniheldur þrjár heiltölur $a_i$, $b_i$, $c_i$, sem tákna göng á milli gatnamóta $a_i$ og $b_i$. Gildið $c_i$ er efri mörk á fjölda leiða sem geta legið í gegnum þessi göng.

Úttak

Í fyrstu og einu línunni skaltu prenta eina heiltölu sem táknar hámarks heildarlengd stiga á milli völdu stöðvaparanna.

Ef engin leið er til að para stöðvarnar saman þannig að skorðurnar séu uppfylltar, prentaðu $-1$.

Takmarkanir

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, öll gatnamót eru tengd og fjöldi stöðva (þ.e. botnlanga) er slétt tala.

Dæmi

Inntak 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

Úttak 1

10

Athugasemd

Í fyrsta dæminu gefur tenging stöðva á gatnamótum $5\text{--}9$, $6\text{--}7$ og $8\text{--}10$ heildarlengd lestarleiða sem er jöfn $4 + 3 + 3 = 10$.

Inntak 2

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

Úttak 2

-1