중앙 트리

트리는 사이클이 없는 연결 그래프이다.

어떤 정점에서 다른 모든 정점까지의 (가중치) 거리 합이 가장 작은 정점을 중앙 정점이라고 하자. 정점 수가 적을 때에는 모든 정점을 하나씩 시도해 보는 것으로 쉽게 찾을 수 있다.

예를 들어 정점이 5개인 다음 트리를 생각하자. 정점을 각각 $A, B, C, D, E$라고 부르면 간선과 가중치는 다음과 같다.

• $B - A$ : 2
• $B - C$ : 1
• $B - D$ : 7
• $D - E$ : 5

이 트리에서 중앙 정점은 $B$이며, $B$에서 각 정점까지의 거리는 $B \to A = 2,\quad B \to C = 1,\quad B \to D = 7,\quad B \to E = 7 + 5 = 12$ 이므로 그 합은 $2 + 1 + 7 + 12 = 22$이다.

정점 수 $N$이 큰 경우에도 풀 수 있도록, 트리를 입력받아 모든 정점에서 중앙 정점까지의 거리 합(즉, 위에서 정의한 최소 합)을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 트리의 정점 수 $n$이 주어진다. ($1 \le n \le 10{,}000$) 정점은 $0$번부터 $n-1$번까지 번호가 매겨져 있다.

이어지는 $n-1$개의 줄에는 각각 세 정수 $a$, $b$, $w$가 주어진다. ($1 \le w \le 100$) 이는 정점 $a$와 $b$를 잇는 가중치 $w$인 간선을 의미한다.

입력의 마지막 줄에는 $0$이 하나 주어지며, 이는 입력의 끝을 나타낸다.

각 테스트 케이스마다 모든 정점에서 중앙 정점까지의 거리 합(가능한 최소 합)을 한 줄에 하나씩 출력한다.