I nani hanno appena costruito il loro nuovo villaggio sotterraneo. Ora è il momento di pianificare la rete ferroviaria che opererà al suo interno.

Il villaggio è composto da $N$ incroci e $N - 1$ tunnel che li collegano. I tunnel sono stati costruiti in modo tale che sia possibile raggiungere qualsiasi incrocio da qualsiasi altro. Ad ogni incrocio che è un vicolo cieco (cioè collegato da un solo tunnel), c'è una stazione ferroviaria.

Il tuo compito è determinare i percorsi dei treni nel villaggio. Per soddisfare le richieste dei nani, tutte le stazioni devono essere accoppiate (fortunatamente ce n'è un numero pari), e ci sarà un treno in servizio tra ogni coppia, utilizzando il percorso più breve possibile. I tunnel hanno però delle limitazioni. Sebbene ogni tunnel abbia la stessa lunghezza (uguale a $1$), la loro larghezza consente il passaggio solo a un numero limitato di percorsi.

I nani vogliono che la lunghezza totale dei percorsi dei treni sia la più grande possibile. Sai calcolare quale può essere la lunghezza massima?

Input

La prima riga di input contiene un intero $N$, che rappresenta il numero di incroci nel villaggio.

Ciascuna delle successive $N - 1$ righe contiene tre interi $a_i$, $b_i$, $c_i$, che rappresentano un tunnel tra gli incroci $a_i$ e $b_i$. Il valore $c_i$ è un limite superiore al numero di percorsi che possono passare attraverso questo tunnel.

Output

Nella prima e unica riga, stampa un singolo intero che rappresenta la lunghezza totale massima dei percorsi tra le coppie di stazioni scelte.

Se non c'è modo di accoppiare le stazioni soddisfacendo i vincoli, stampa $-1$.

Limiti

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, tutti gli incroci sono connessi e il numero di stazioni (cioè di vicoli ciechi) è pari.

Esempi

Input 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

Output 1

10

Note

Nel primo esempio, collegando le stazioni agli incroci $5\text{--}9$, $6\text{--}7$ e $8\text{--}10$ si ottiene una lunghezza totale dei percorsi dei treni pari a $4 + 3 + 3 = 10$.

Input 2

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

Output 2

-1