북쪽 나라의 도로

면접 대비

시간 제한1초메모리 제한128 MB

요약

최대 10,000개 도시로 이루어진 가중치 트리의 도로 정보가 주어질 때, 가장 먼 두 도시 사이의 거리(지름)를 구합니다.

문제

두 도시 사이에 도로를 놓는 데는 큰 비용이 든다. 그래서 북쪽 나라는 어떤 도시도 두 번 이상 지나지 않고 임의의 두 도시 사이를 이동하는 경로가 항상 하나뿐이 되도록 도로망을 설계했다.

또한 모든 도시는 다른 모든 도시로 이동할 수 있다. 이때 서로 가장 멀리 떨어진 두 도시 사이의 거리를 구하라.

도시는 최대 10,000개이며, 1번부터 번호가 붙어 있다.

입력은 파일의 끝까지 여러 줄로 주어진다. 각 줄에는 세 양의 정수 u, v, w가 주어진다. 이는 서로 다른 두 도시 u, v를 잇는 양방향 도로의 길이가 w임을 뜻한다.

가장 멀리 떨어진 두 도시 사이의 거리를 정수 하나로 출력한다.