Kääpiöt ovat juuri rakentaneet uuden maanalaisen kylänsä. Nyt on aika suunnitella rautatieverkosto, joka toimii sen sisällä.
Kylä koostuu $N$ risteyksestä ja niitä yhdistävästä $N - 1$ tunnelista. Tunnelit on rakennettu siten, että mistä tahansa risteyksestä pääsee mihin tahansa muuhun risteykseen. Jokaisessa risteyksessä, joka on umpikuja (mikä tarkoittaa, että siihen johtaa vain yksi tunneli), on rautatieasema.
Tehtävänäsi on määrittää junien reitit kylässä. Kääpiöiden vaatimusten täyttämiseksi kaikki asemat on muodostettava pareiksi (onneksi niitä on parillinen määrä), ja jokaisen parin välillä liikennöi yksi juna käyttäen lyhintä mahdollista reittiä. Tunneleilla on kuitenkin rajoituksensa. Vaikka jokainen tunneli on samanpituinen (pituudeltaan $1$), niiden leveys sallii vain rajoitetun määrän reittejä kulkea niiden läpi.
Kääpiöt haluavat junareittien kokonaispituuden olevan mahdollisimman suuri. Voitko laskea, mikä suurin mahdollinen pituus voi olla?
Syöte
Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $N$, joka kuvaa kylän risteysten lukumäärää.
Jokainen seuraavista $N - 1$ rivistä sisältää kolme kokonaislukua $a_i$, $b_i$, $c_i$, jotka kuvaavat tunnelia risteysten $a_i$ ja $b_i$ välillä. Arvo $c_i$ on yläraja tämän tunnelin läpi kulkevien reittien lukumäärälle.
Tuloste
Tulosta ensimmäiselle ja ainoalle riville yksi kokonaisluku, joka kuvaa valittujen asemaparien välisten polkujen suurinta mahdollista kokonaispituutta.
Jos asemia ei ole mahdollista muodostaa pareiksi rajoituksia noudattaen, tulosta $-1$.
Rajoitukset
$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, kaikki risteykset ovat yhteydessä toisiinsa, ja asemien (eli umpikujien) lukumäärä on parillinen.
Esimerkit
Syöte 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
Tuloste 1
10
Huomautus
Ensimmäisessä esimerkissä asemien yhdistäminen risteyksissä $5\text{--}9$, $6\text{--}7$ ja $8\text{--}10$ antaa junareittien kokonaispituudeksi $4 + 3 + 3 = 10$.
Syöte 2
5 1 2 3 1 3 1 1 4 0 1 5 2
Tuloste 2
-1