Un árbol genético es un árbol que muestra la evolución de distintos genes o especies biológicas. Representa el parentesco de genes específicos almacenados en los nodos hoja sin suposiciones sobre sus ancestros. Los nodos hoja representan genes, llamados taxones, y los nodos internos representan supuestos taxones ancestrales. Cada arista tiene asociado un entero positivo, la longitud filogenética, que cuantifica la distancia evolutiva entre sus dos nodos. Por ejemplo, la figura de la izquierda muestra un árbol genético con seis hojas, que aproxima la relación entre seis taxones, y la de la derecha muestra un árbol con cuatro taxones.

Figura B.1: Árboles genéticos sin raíz $T_1,T_2$.

Como los árboles $T_1,T_2$ anteriores, los árboles genéticos se modelan como árboles sin raíz donde cada nodo interno (no hoja) tiene grado tres. La longitud de camino entre dos hojas es la suma de las longitudes filogenéticas de las aristas del único camino entre ellas. En $T_1$, la longitud entre Human y Cow es $2+3=5$ y entre Human y Goldfish es $2+4+8+10=24$. Estas longitudes indican que genéticamente Human está mucho más cerca de Cow que de Goldfish. A partir de $T_2$ podemos deducir que el primate más cercano a Human es Chimpanzee.

Los investigadores están interesados en medir la distancia entre los genes del árbol. Una medida de distancia conocida es la suma de los cuadrados de las longitudes de camino de todos los pares de hojas sin orden. Más precisamente, esta distancia $d(T)$ se define así:

$$d(T)=\sum_{\text{par sin orden }(u,v)}p_{u,v}^2.$$

Donde $p_{u,v}$ es la longitud de camino entre dos hojas $u,v$ de $T$. Observa que $d(T)$ es la suma de los cuadrados de las longitudes $p_{u,v}^2$ sobre todos los pares de hojas sin orden $u,v$ de $T$. Para el árbol genético $T_2$ de la figura B.1, hay seis caminos correspondientes a todos los pares de hojas sin orden: (Human, Chimpanzee), (Human, Gorilla), (Human, Orangutan), (Chimpanzee, Gorilla), (Chimpanzee, Orangutan) y (Gorilla, Orangutan). La suma de los cuadrados de las longitudes es $2^2+4^2+5^2+4^2+5^2+5^2=111$, por lo que $d(T_2)=111$.

Dado un árbol genético sin raíz $T$, escribe un programa que imprima $d(T)$.

Entrada

Tu programa debe leer de la entrada estándar. La entrada comienza con una línea que contiene un entero $n$ ($4\le n\le100\,000$), donde $n$ es el número de nodos del árbol genético de entrada $T$. Entonces $T$ tiene $n-1$ aristas. Sus nodos se numeran del $1$ al $n$. Las siguientes $n-1$ líneas representan las $n-1$ aristas de $T$; cada línea contiene tres enteros no negativos $a,b,l$ ($1\le a\ne b\le n$, $1\le l\le50$), donde los nodos $a,b$ forman una arista con longitud filogenética $l$.

Salida

Tu programa debe escribir en la salida estándar. Imprime exactamente una línea, que debe contener un entero positivo $d(T)$.

A continuación se muestran entradas y salidas de ejemplo para tres casos de prueba.

Ejemplos

Entrada 1

4
1 4 1
4 3 1
2 4 1

Salida 1

12

Entrada 2

6
1 5 1
5 2 1
5 6 1
6 4 3
6 3 2

Salida 2

111

Entrada 3

10
1 2 10
10 2 7
3 2 8
3 9 3
9 8 2
7 9 1
6 4 3
4 5 2
3 4 4

Salida 3

4709