시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 55 25 20 48.780%

문제

두더지가 정보섬에 올라왔다!

두더지는 정보섬 지하에 여러 채의 자택을 소유하고 있다. 두더지는 집 사이를 오가는 걸 좋아한다. 정보섬에는 총 N개의 두더지 집이 있으며 이 집들은 N-1개의 길로 연결되어 있다. 임의의 집에서 또 다른 집으로 가는 경로는 항상 유일하게 하나만 존재한다. 즉, 두더지 집들은 트리 형태로 모두 연결되어 있다. 어떤 길을 지날 때, 두더지는 W만큼의 만족도를 얻는다.

어느 날, 아래의 그림과 같은 집을 가진 두더지는 집1에서 집4로 이동했다. 이때 거치게 되는 집은 (1 → 2 → 3 → 4)이다. 두더지는 한 번 이동할 때마다, 이동경로에 포함되는 만족도들 중에서 가장 최소인 만족도를 얻는다. 즉, (1 → 4)의 경우에는 만족도를 2만큼, (6 → 2)의 경우에는 만족도를 3만큼 얻게 된다.


 

 

두더지는 갑자기 모든 집의 쌍 (a, b)에 대한 이동을 끝냈을 때 얻을 수 있는 만족도의 총합이 얼마인지 궁금해졌다. (a, b)와 (b, a)는 같은 경로로 친다. 즉, 위의 그림의 경우 (1-2, 1-3, 1-4, 1-5, 1-6, 2-3, 2-4, 2-5, 2-6, 3-4, 3-5, 3-6, 4-5, 4-6, 5-6)를 모두 이동했을때 얻는 만족도의 총합을 말한다.

하지만 두더지는 계산하다가 지쳐 이내 잠에 들고 말았다! 착한 여러분들이 잠든 두더지를 대신해 계산해 주자.

입력

첫째 줄에 집의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

이후 N-1개의 줄에 걸쳐 X, Y, W가 주어진다. 이는 집 X와 Y가 연결되어 있고, 이 길을 지날 때의 만족도가 W라는 뜻이다. (1 ≤ X,Y ≤ N, 1 ≤ W ≤ 200) 

출력

문제에 제시된 이동을 끝냈을 때, 두더지가 느끼는 만족도의 총합을 출력한다.

예제 입력 1

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

예제 출력 1

40