겨울 제설 작업

바이트랜드에 겨울이 찾아왔습니다. 제설차 운전사 바이트아자르는 당황하지 않고 바이트타운의 거리를 치우러 나섰습니다.

바이트타운의 도로망은 $n$개의 교차로가 $n - 1$개의 양방향 도로로 이어져 있습니다. 임의의 교차로에서 다른 임의의 교차로로 가는 길은, 하나 이상의 도로로 이루어진 경로가 정확히 하나만 존재합니다. 즉 도로망은 트리 구조입니다.

눈은 계속 내리므로 도로는 몇 번이고 다시 치워야 합니다. 바이트아자르는 각 도로마다 하루 동안 최소 몇 번 치워야 하는지 알고 있습니다(하루 중 언제 치우는지는 상관없습니다). 그는 어느 교차로에서든 제설을 시작할 수 있습니다. 지나간 도로의 총 횟수가 최소가 되도록 작업을 계획하려고 합니다. 같은 도로를 여러 번 지나가면 지나간 횟수만큼 모두 셉니다.

제설차는 하나의 연속된 경로로만 이동합니다. 즉, 연달아 지나는 두 도로는 반드시 한 교차로를 공유해야 하며, 출발한 교차로와 다른 교차로에서 작업을 마쳐도 됩니다.

첫째 줄에 바이트타운의 교차로 수 $n$ ($2 \le n \le 500\,000$)이 주어집니다. 다음 $n - 1$개의 줄에는 각 도로가 세 정수 $a_i$, $b_i$, $d_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le d_i \le 100\,000$)로 주어집니다. 이는 교차로 $a_i$와 $b_i$가 양방향 도로로 이어져 있으며, 이 도로를 하루에 최소 $d_i$번 치워야 함을 뜻합니다.

모든 도로를 요구된 횟수 이상 치우기 위해 바이트아자르가 하나의 연속된 경로로 이동할 때 지나가야 하는 도로 통과 횟수의 최솟값을 한 줄에 출력합니다.

예제에서 바이트아자르의 최적 경로는 여덟 번의 도로 통과로 이루어집니다: $1 \to 2 \to 3 \to 5 \to 4 \to 5 \to 6 \to 5 \to 3$.