Dvergene har nettopp bygget sin nye underjordiske landsby. Nå er det på tide å planlegge jernbanenettet som skal være i drift der.
Landsbyen består av $N$ veikryss og $N - 1$ tunneler som forbinder dem. Tunnelene er bygget på en slik måte at det er mulig å nå ethvert veikryss fra ethvert annet. Ved hvert veikryss som er en blindvei (som betyr at det kun er tilkoblet med én tunnel), ligger det en togstasjon.
Din oppgave er å bestemme rutene for togene i landsbyen. For å oppfylle dvergenes krav må alle stasjoner pares sammen (heldigvis er det et partall av dem), og det vil gå ett tog mellom hvert par som bruker den kortest mulige veien. Tunnelene har imidlertid sine begrensninger. Selv om hver tunnel har samme lengde (lik $1$), tillater bredden deres bare et begrenset antall ruter å passere gjennom.
Dvergene ønsker at den totale lengden på togrutene skal være så lang som mulig. Kan du beregne hva den maksimale lengden kan være?
Inndata
Den første linjen i inndataene inneholder ett heltall $N$, som representerer antallet veikryss i landsbyen.
Hver av de neste $N - 1$ linjene inneholder tre heltall $a_i$, $b_i$, $c_i$, som representerer en tunnel mellom veikryssene $a_i$ og $b_i$. Verdien $c_i$ er en øvre grense for antallet ruter som kan passere gjennom denne tunnelen.
Utdata
På den første og eneste linjen skal du skrive ut ett enkelt heltall som representerer den maksimale totale lengden på stiene mellom de valgte parene av stasjoner.
Hvis det ikke finnes noen måte å pare stasjonene på samtidig som kravene oppfylles, skriv ut $-1$.
Begrensninger
$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, alle veikryss henger sammen, og antallet stasjoner (dvs. blindveier) er et partall.
Eksempler
Inndata 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
Forklaring
I det første eksempelet gir det å koble sammen stasjonene ved veikryssene $5\text{--}9$, $6\text{--}7$ og $8\text{--}10$ en total lengde på togrutene lik $4 + 3 + 3 = 10$.
Inndata 2
5 1 2 3 1 3 1 1 4 0 1 5 2
Utdata 2
-1