Los enanos acaban de construir su nueva aldea subterránea. Ahora es el momento de planificar la red de ferrocarriles que operará dentro de ella.

La aldea consta de $N$ intersecciones y $N - 1$ túneles que las conectan. Los túneles se han construido de tal manera que es posible llegar a cualquier intersección desde cualquier otra. En cada intersección que es un callejón sin salida (lo que significa que está conectada por un solo túnel), hay una estación de tren.

Tu tarea es determinar las rutas para los trenes en la aldea. Para cumplir con los requisitos de los enanos, todas las estaciones deben emparejarse (afortunadamente, hay un número par de ellas), y habrá un tren operando entre cada par, utilizando el camino más corto posible. Sin embargo, los túneles tienen sus limitaciones. Aunque cada túnel tiene la misma longitud (igual a $1$), sus anchos permiten que solo pase un número limitado de rutas a través de ellos.

Los enanos quieren que la longitud total de las rutas de tren sea lo más larga posible. ¿Puedes calcular cuál puede ser la longitud máxima?

Entrada

La primera línea de la entrada contiene un entero $N$, que representa el número de intersecciones en la aldea.

Cada una de las siguientes $N - 1$ líneas contiene tres enteros $a_i$, $b_i$, $c_i$, que representan un túnel entre las intersecciones $a_i$ y $b_i$. El valor $c_i$ es un límite superior en el número de rutas que pueden pasar por este túnel.

Salida

En la primera y única línea, imprime un solo entero que represente la longitud total máxima de los caminos entre los pares de estaciones elegidos.

Si no hay forma de emparejar las estaciones cumpliendo las restricciones, imprime $-1$.

Límites

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, todas las intersecciones están conectadas, y el número de estaciones (es decir, callejones sin salida) es par.

Ejemplos

Entrada 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

Salida 1

10

Nota

En el primer ejemplo, conectar las estaciones en las intersecciones $5\text{--}9$, $6\text{--}7$ y $8\text{--}10$ da una longitud total de rutas de tren igual a $4 + 3 + 3 = 10$.

Entrada 2

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

Salida 2

-1