’S No Problem

눈이 많이 내리는 북부 스노우블로비아에 자리한 Yllihc 공과대학(YETI)에는 두 가지 문제가 있다. 눈과 돈이다. 정확히는 눈이 너무 많고 돈이 너무 없다. 겨울마다(사실 가을과 봄에도) 캠퍼스는 눈으로 덮이고, 건물들을 잇는 인도는 지나다닐 수 없게 된다. YETI가 계속 기능하려면 캠퍼스 건물들을 잇는 인도의 눈을 치워야 한다. 예산이 빠듯해서 이 인도들은 어떤 두 건물 사이에도 경로가 존재하도록 하는 최소한의 집합이다.

인도를 더 짓지 않아 아낀 돈으로 YETI는 제설기를 두 대 샀다. 제설기로 눈을 치우려면 직원 두 명이 제설기를 보관한 건물(또는 건물들)에서 제설기를 꺼내 인도를 따라 밀면서 눈을 치운다. 모든 인도는 적어도 한 번은 지나가야 한다. 제설기는 각각 작업을 마친 뒤 현재 옆에 있는 건물에 보관된다(그리고 다음번 눈이 내리면 제설기는 반대 방향으로 밀린다. 눈이 내리는 열한 달 내내 이렇게 반복된다).

YETI 정비팀은 제설기의 보관 건물을 정하고 제설기를 미는 경로를 설계해서, 두 기계가 추위 속에서 이동하는 총 거리를 최소화하려 한다(값비싼 장비와 직원 모두 얼어붙지 않도록). 경로에는 이미 눈이 치워진 인도를 따라 미는 경우도 있다. 그림 J.1은 예제 입력 1의 인도 배치에 대한 최적해 하나를 보여 준다.

그림 J.1: 예제 입력 1에 대한 최적 경로 한 쌍을 보여 주는 그림.

YETI는 컴퓨터과학과에 이 문제를 맡기려 했지만, 그 학과는 ’06년 대폭풍으로 사라졌다. 그래서 YETI는 당신에게 도움을 청했다.

첫째 줄에 YETI 캠퍼스의 건물 수를 나타내는 정수 n (4 ≤ n ≤ 100 000)이 주어진다. 건물은 1부터 n까지 번호가 붙어 있다. 이어지는 n − 1개 줄 각각에는 건물 a와 b 사이에 길이 d인 인도가 있음을 나타내는 세 정수 a, b, d (1 ≤ a, b ≤ n; a ≠ b; 1 ≤ d ≤ 500)가 주어진다.

제설기가 모든 인도의 눈을 치우기 위해 이동해야 하는 최소 총 거리를 출력한다.