구슬과 끈 Batch 컴파일 명령

레오나르도 다빈치 시절에 구슬과 끈이라고 불리는 유명한 게임이 있었다. 이 게임은 (당연하게도) 구슬과 끈으로 하는 것이다. 끈은 파란 색과 붉은 색의 두 가지 종류가 있다. 구슬들은 1부터 $n$까지 번호가 붙어 있다.게임의 시작에는 단 하나의 구슬만 있고 이후 다음과 같은 두 가지 작업 중 하나를 선택하여 구슬과 끈을 추가한다.

• Append($w$, $v$): 새로운 구슬 $w$가 이미 존재하는 구슬 $v$에 붉은 끈을 이용하여 연결된다.
• Insert($w$, $u$, $v$): 새로운 구슬 $w$가 $u$와 $v$ 사이에 끼워지는데, 이미 존재하는 $u$와 $v$ 사이의 붉은 끈을 제거하고 두 개의 파란 끈을 추가하는 방식으로 진행된다. 즉, 이미 존재하는 붉은 끈인 $u$-$v$가 새로운 두 개의 파란 끈 $u-w$와 $w-v$로 교체된다.

파란 색과 붉은 색의 모든 끈은 특정한 길이를 가진다. 게임이 다 끝났을 때 중요한 것은 파란 끈들의 길이의 합이다. (붉은 끈의 길이는 중요하지 않다는 뜻이다.) 파란 끈들의 길이의 합을 최종 점수라고 부른다.

입력으로 주어지는 것은 구슬들이 끈으로 연결된 형태와 각 끈의 길이들이다. 하지만, 끈의 색은 주어지지 않는다.

주어진 연결 형태와 끈의 길이들에 대해서 가장 높은 최종 점수를 받을 수 있는 방법을 알아내어 그 점수를 출력하는 프로그램을 작성하시오. 좀더 정확히 말하자면, 주어진 연결 형태를 얻게 되는 모든 가능한 구슬과 끈 게임의 진행 과정들 중에 가장 높은 최종 점수(푸른 끈들의 길이의 합)를 얻게 되는 진행 과정을 찾아서 그 점수를 출력해야 하는 것이다.

입력

입력의 첫 번째 줄에는 구슬의 개수 $n$이 양의 정수로 주어진다. 구슬들은 1부터 $n$까지 번호가 붙어 있다. 이후 $n-1$개의 줄들에는 각각 3개의 자연수가 주어지는데, 첫 번째와 두 번째 수는 연결된 구슬의 번호이고, 세 번째 수는 그 두 구슬을 연결하는 끈의 길이이다. 번호는 1 이상 $n$ 이하의 자연수이고, 끈의 길이는 1 이상 $10,000$ 이하의 자연수이다.

출력

출력은 한 줄로서 가능한 가장 높은 최종 점수를 자연수로 출력한다.

입출력 예

추가 설명

첫 번째 입출력 예의 경우에 최종 점수 60점을 얻는 방법은 다음과 같다.

• 3번 구슬로 시작.
• 5번을 3번에 붙임 (끈 길이 무관함).
• 3 ? 5사이에 1을 끼워 넣음 (끈 길이는 각각 40과 20).
• 2번을 1번에 길이 10인 끈으로 붙임.
• 4번을 1번에 길이 15인 끝으로 붙임.

이렇게 진행하면 아래 그림과 같은 연결 형태를 얻는다. 자세히 조사하면, 동일한 연결 상태를 만드는 다른 방법들로는 더 높은 최종 점수를 얻을 수 없음을 확인할 수 있다.

두 번째 입출력 예의 경우에 최적의 결과를 얻으면 다음과 같으며, 최종 점수는 140점이다.

채점 기준

서브태스크 1 (13점)

$1 \le n \le 10$

서브태스크 2 (15점)

$1 \le n \le 200$

서브태스크 3 (29점)

$1 \le n \le 10000$

서브태스크 4 (43점)

$1 \le n \le 200000$