유전자 트리는 다양한 유전자 또는 생물 종의 진화를 나타내는 트리이다. 유전자 트리는 조상에 대한 가정 없이 리프 정점에 저장된 특정 유전자 사이의 관계를 나타낸다. 리프 정점은 분류군(taxa)이라 부르는 유전자를 나타내고, 내부 정점은 추정되는 조상 분류군을 나타낸다. 트리의 각 간선에는 계통발생 길이라는 양의 정수가 연결되어 있으며, 이는 간선의 두 정점 사이의 진화적 거리를 정량화한다. 예를 들어 아래 왼쪽 그림은 여섯 분류군 사이의 관계를 근사하는, 리프 정점이 여섯 개인 유전자 트리이고, 오른쪽 그림은 분류군이 네 개인 유전자 트리이다.

그림 B.1: 루트 없는 유전자 트리 $T_1,T_2$.

위의 $T_1,T_2$처럼 유전자 트리는 모든 내부 정점(리프가 아닌 정점)의 차수가 3인 루트 없는 트리로 모델링된다. 두 리프 정점 사이의 경로 길이는 두 정점을 잇는 유일한 경로의 간선들의 계통발생 길이 합이다. $T_1$에서 Human과 Cow 사이의 경로 길이는 $2+3=5$이고 Human과 Goldfish 사이의 경로 길이는 $2+4+8+10=24$이다. 이 길이들은 유전적으로 Human이 Goldfish보다 Cow에 훨씬 더 가깝다는 것을 나타낸다. $T_2$에서는 Human에 가장 가까운 영장류가 Chimpanzee라고 추측할 수 있다.

연구자들은 트리의 유전자 사이의 거리를 측정하는 데 관심이 있다. 잘 알려진 거리 척도는 순서 없는 모든 리프 쌍의 경로 길이를 제곱한 값의 합이다. 더 정확히 말하면, 이러한 거리 $d(T)$는 다음과 같이 정의된다.

$$d(T)=\sum_{\text{순서 없는 쌍 }(u,v)}p_{u,v}^2.$$

여기서 $p_{u,v}$는 $T$의 두 리프 정점 $u,v$ 사이의 경로 길이이다. $d(T)$는 $T$의 순서 없는 모든 리프 쌍 $u,v$에 대한 제곱 경로 길이 $p_{u,v}^2$의 합임에 유의하라. 그림 B.1의 유전자 트리 $T_2$에는 순서 없는 모든 리프 쌍에 대해 여섯 경로가 있다: (Human, Chimpanzee), (Human, Gorilla), (Human, Orangutan), (Chimpanzee, Gorilla), (Chimpanzee, Orangutan), (Gorilla, Orangutan). 제곱 경로 길이의 합은 $2^2+4^2+5^2+4^2+5^2+5^2=111$이므로 $d(T_2)=111$이다.

루트 없는 유전자 트리 $T$가 주어졌을 때 $d(T)$를 출력하는 프로그램을 작성하라.

입력

프로그램은 표준 입력에서 읽어야 한다. 입력은 입력 유전자 트리 $T$의 정점 수인 정수 $n$ ($4\le n\le100\,000$)이 있는 줄로 시작한다. 그러면 $T$에는 $n-1$개의 간선이 있다. $T$의 정점은 $1$부터 $n$까지 번호가 매겨져 있다. 다음 $n-1$개 줄은 $T$의 $n-1$개 간선을 나타낸다. 각 줄에는 음이 아닌 세 정수 $a,b,l$ ($1\le a\ne b\le n$, $1\le l\le50$)이 있으며, 두 정점 $a,b$가 계통발생 길이 $l$의 간선을 이룬다.

출력

프로그램은 표준 출력에 써야 한다. 정확히 한 줄을 출력한다. 그 줄에는 양의 정수 $d(T)$ 하나가 있어야 한다.

아래는 세 테스트 케이스의 예제 입력과 출력이다.

예제

입력 1

4
1 4 1
4 3 1
2 4 1

출력 1

12

입력 2

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

출력 2

111

입력 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

출력 3

4709