고속도로 건설

접근성 통근 운동(Accessible Commuting Movement, ACM)의 대표인 당신은 시장에게 새 고속도로 건설을 계속 건의해 왔고, 마침내 오늘 요청이 승인되었습니다. 단, 한 가지 조건이 있습니다. 건설할 단 하나의 최적 고속도로 계획을 제출해야 한다는 것입니다.

당신에게는 도시의 모든 마을이 표시된 지도가 있습니다. 각 마을에는 고유한 번호가 붙어 있으며, 어느 마을에나 고속도로 진입로(on-ramp)를 놓을 수 있습니다. 지도에는 마을 쌍을 잇는 도로들이 있고, 각 도로에는 주행 거리가 적혀 있습니다. 이 도로망에서 임의의 두 마을 사이에는 정확히 하나의 경로만 존재합니다. 즉, 마을과 도로는 하나의 트리를 이룹니다.

당신은 원하는 두 마을 사이를 왕복하는 고속도로 하나를 건설합니다. 이 고속도로는 두 마을 사이의 유일한 도로 경로를 대체하며, 그 경로 위의 모든 마을에는 진입로가 생깁니다. 진입로가 없는 마을의 주민은 고속도로를 이용하기 위해 남은 도로를 따라 진입로가 있는 가장 가까운 마을까지 운전해서 가야 합니다.

긴 통근은 바람직하지 않으므로, 어떤 마을에서든 가장 가까운 진입로까지 가는 가장 긴 운전 거리가 최소가 되도록 고속도로를 놓으려고 합니다. 도로와 주행 거리가 표시된 지도가 주어질 때, 고속도로가 완성된 뒤 어떤 주민이든 가장 가까운 진입로에 도달하기 위해 운전해야 하는 가장 먼 거리를 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 하나의 도시 지도를 나타내며, 마을의 수를 뜻하는 정수 $N$ ($2 \le N \le 100000$)이 적힌 한 줄로 시작합니다. 이어지는 $N - 1$개의 줄에는 각각 세 정수 $i$, $j$ ($1 \le i, j \le N$), $d$ ($1 \le d \le 10000$)가 주어지며, 이는 마을 $i$와 $j$가 주행 거리 $d$인 도로로 연결되어 있음을 뜻합니다. 각 지도의 마을과 도로는 하나의 트리를 이룹니다. 입력의 끝은 $N = 0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 도시 지도마다, 가장 가까운 진입로까지의 거리가 최소가 되도록 고속도로를 놓았을 때 어떤 마을에서든 가장 가까운 진입로까지의 가장 먼 거리를 정수 하나로 한 줄에 출력하세요.