Drzewo genowe to drzewo przedstawiające ewolucję różnych genów lub gatunków biologicznych. Przedstawia pokrewieństwo konkretnych genów zapisanych w liściach, bez założeń o ich przodkach. Liście reprezentują geny, nazywane taksonami, a wierzchołki wewnętrzne reprezentują domniemane taksony przodków. Każdej krawędzi przypisana jest dodatnia liczba całkowita, długość filogenetyczna, określająca ilościowo odległość ewolucyjną między jej końcami. Na przykład lewy rysunek poniżej przedstawia drzewo genowe o sześciu liściach, przybliżające relację między sześcioma taksonami, a prawy drzewo z czterema taksonami.

Rysunek B.1: Nieukorzenione drzewa genowe $T_1,T_2$.

Podobnie jak powyższe drzewa $T_1,T_2$, drzewa genowe modeluje się jako nieukorzenione drzewa, w których każdy wierzchołek wewnętrzny (niebędący liściem) ma stopień trzy. Długość ścieżki między dwoma liśćmi jest sumą długości filogenetycznych krawędzi na jedynej ścieżce między nimi. W $T_1$ długość ścieżki między Human i Cow wynosi $2+3=5$, a między Human i Goldfish $2+4+8+10=24$. Długości te wskazują, że genetycznie Human jest znacznie bliżej Cow niż Goldfish. Z $T_2$ możemy wywnioskować, że najbliższym Human naczelnym jest Chimpanzee.

Badacze interesują się mierzeniem odległości między genami w drzewie. Znana miara odległości to suma kwadratów długości ścieżek dla wszystkich nieuporządkowanych par liści. Dokładniej, taką odległość $d(T)$ definiujemy następująco:

$$d(T)=\sum_{\text{nieuporządkowana para }(u,v)}p_{u,v}^2.$$

Tutaj $p_{u,v}$ jest długością ścieżki między dwoma liśćmi $u,v$ w $T$. Zauważ, że $d(T)$ jest sumą kwadratów długości ścieżek $p_{u,v}^2$ po wszystkich nieuporządkowanych parach liści $u,v$ w $T$. Dla drzewa genowego $T_2$ z rysunku B.1 jest sześć ścieżek dla wszystkich nieuporządkowanych par liści: (Human, Chimpanzee), (Human, Gorilla), (Human, Orangutan), (Chimpanzee, Gorilla), (Chimpanzee, Orangutan) oraz (Gorilla, Orangutan). Suma kwadratów długości ścieżek to $2^2+4^2+5^2+4^2+5^2+5^2=111$, więc $d(T_2)=111$.

Dane jest nieukorzenione drzewo genowe $T$. Napisz program wypisujący $d(T)$.

Wejście

Program czyta ze standardowego wejścia. Wejście zaczyna się od wiersza z liczbą całkowitą $n$ ($4\le n\le100\,000$), będącą liczbą wierzchołków wejściowego drzewa genowego $T$. Drzewo $T$ ma wtedy $n-1$ krawędzi. Wierzchołki $T$ są ponumerowane od $1$ do $n$. Następne $n-1$ wierszy reprezentuje $n-1$ krawędzi $T$; każdy zawiera trzy nieujemne liczby całkowite $a,b,l$ ($1\le a\ne b\le n$, $1\le l\le50$), gdzie wierzchołki $a,b$ tworzą krawędź o długości filogenetycznej $l$.

Wyjście

Program zapisuje na standardowe wyjście. Wypisz dokładnie jeden wiersz. Powinien zawierać jedną dodatnią liczbę całkowitą $d(T)$.

Poniżej przedstawiono przykładowe wejścia i wyjścia dla trzech przypadków testowych.

Przykład

Wejście 1

4
1 4 1
4 3 1
2 4 1

Wyjście 1

12

Wejście 2

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

Wyjście 2

111

Wejście 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

Wyjście 3

4709