산타의 선물 배달

크리스마스 이브, 산타 할아버지는 루트(1번)에서 출발하여 트리 구조로 연결된 N개의 집을 모두 방문하고 다시 루트로 돌아와야 한다. 각 간선의 길이가 주어질 때, 산타가 이동해야 하는 최소 거리를 구하시오.

트리이므로 모든 간선을 정확히 두 번(왕복) 방문하는 것이 최적이다.

입력

첫째 줄에 집의 수 N이 주어진다. 다음 N-1줄에 간선 정보 (U V W) — U와 V를 잇는 길이 W의 간선이 주어진다.

• 2 ≤ N ≤ 100,000
• 1 ≤ W ≤ 100,000

출력

산타가 이동해야 하는 최소 총 거리를 출력한다.

예제 입력

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

예제 출력

22