Les nains viennent de construire leur nouveau village souterrain. Il est maintenant temps de planifier le réseau ferroviaire qui y fonctionnera.

Le village se compose de $N$ intersections et de $N - 1$ tunnels les reliant. Les tunnels ont été construits de telle manière qu'il est possible d'atteindre n'importe quelle intersection depuis n'importe quelle autre. À chaque intersection qui est un cul-de-sac (c'est-à-dire qu'elle n'est reliée que par un seul tunnel), il y a une gare.

Votre tâche consiste à déterminer les itinéraires des trains dans le village. Pour répondre aux exigences des nains, toutes les gares doivent être associées par paires (heureusement, il y en a un nombre pair), et il y aura un train circulant entre chaque paire, en empruntant le chemin le plus court possible. Les tunnels ont cependant leurs limites. Bien que chaque tunnel ait la même longueur (égale à $1$), leur largeur ne permet qu'à un nombre limité d'itinéraires d'y passer.

Les nains veulent que la longueur totale des itinéraires de train soit aussi grande que possible. Pouvez-vous calculer quelle peut être cette longueur maximale ?

Entrée

La première ligne de l'entrée contient un entier $N$, représentant le nombre d'intersections dans le village.

Chacune des $N - 1$ lignes suivantes contient trois entiers $a_i$, $b_i$, $c_i$, représentant un tunnel entre les intersections $a_i$ et $b_i$. La valeur $c_i$ est la limite supérieure du nombre d'itinéraires pouvant passer par ce tunnel.

Sortie

Sur la première et unique ligne, affichez un seul entier représentant la longueur totale maximale des chemins entre les paires de gares choisies.

S'il n'y a aucun moyen d'associer les gares par paires tout en satisfaisant les contraintes, affichez $-1$.

Contraintes

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, toutes les intersections sont connectées, et le nombre de gares (c'est-à-dire de culs-de-sac) est pair.

Exemples

Entrée 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

Sortie 1

10

Note

Dans le premier exemple, relier les gares aux intersections $5\text{--}9$, $6\text{--}7$ et $8\text{--}10$ donne une longueur totale d'itinéraires de train égale à $4 + 3 + 3 = 10$.

Entrée 2

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

Sortie 2

-1