시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 24 9 8 47.059%

문제

텔레토비 동산에 사는 너구리 구구는 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 n개의 방을 가지고 있다. 구구의 집으로 들어가는 입구는 한 개이며, 입구와 모든 방은 총 n개의 길로 이어져 있다. 구구는 무더운 여름 햇살을 피해 스머프 동산에서 발견한 멜론아 아이스크림을 지면과 가장 먼 방에 숨기려 한다.

하지만 구구는 집안에 들어가는 순간 방향감각을 잃는다. 구구는 깊은 고민 끝에 최대한 입구에서 먼 방에 아이스크림을 숨기기로 한다.

입구와 방, 방과 방의 거리는 입력으로 주어진다.

구구가 집 입구에서 멜론아 아이스크림을 숨기기 위해 이동해야 하는 거리가 몇 미터인지 출력하라.

입력

첫째 줄에 n(1 ≤ n ≤ 5000)이 주어진다. 다음 n-1개의 줄에 서로 이어진 두 개의 방 a, bab사이의 거리 c(1 ≤ a, bn, 1 ≤ c ≤ 1,000,000,000)가 주어진다. 1은 입구를 의미한다.

출력

구구가 집 입구에서 멜론아 아이스크림을 숨기기 위해 이동해야 하는 거리가 몇 미터인지 출력하라.

예제 입력 1

4
1 2 3
2 3 2
2 4 4

예제 출력 1

7