문제
지하철 망이 있다. 이 지하철 망은 하나의 순환선과 이 순환선상의 역에 연결되는 지선들로 구성되어 있고, 각 지선은 트리 형태이다. 각 역에는 지선들이 없을 수도 있어서, 지하철이 순환선만으로 구성될 수도 있다. 모든 역은 1부터 N까지의 번호로 나타낸다. 아래 그림은 이러한 형태의 지하철 망의 예를 보여준다. 그림에서 정점은 지하철역을 나타내고, 간선은 두 역을 잇는 선로를 나타내며 간선상의 값은 선로를 지나는데 걸리는 시간을 나타낸다. 지하철 망의 역의 개수와 선로의 개수는 항상 같음에 유의하라.
지하철 사고 발생 시 응급치료를 위하여 2개의 역에 응급센터를 설치하기로 하였다. 각 역의 응급대처시간은 가까운 응급센터까지 가는데 걸리는 최단 시간이다. 모든 역들의 응급대처시간 중 가장 긴 시간이 최소가 되도록 2 개의 응급센터 설치 역을 구하는 프로그램을 작성하시오.
위의 그림에서 역 8과 역 12에 응급센터를 설치할 경우, 역 1에서부터 역 12까지의 응급대처시간은 각각 11, 13, 8, 6, 13, 11, 5, 0, 12, 7, 10, 0으로서 가장 긴 시간은 13이다. 또한, 두 응급센터를 어디에 설치하더라도, 모든 역들의 응급대처시간 중 가장 긴 시간은 13보다 작아지지 않는다.
입력
첫째 줄에 역의 개수(선로의 개수)인 N(3≤N≤50,000)이 주어진다. 다음 줄부터 N줄에 걸쳐 각 줄에 하나의 선로를 나타내는 세 개의 양의 정수 u, v, x가 주어진다. 여기서 u, v는 선로를 통해 연결되는 두 역의 번호이고, x는 이 선로를 지나는데 걸리는 시간이다. 단, x는 1 이상 10,000 이하이다.
출력
첫째 줄에 응급센터를 설치하는 두 역의 번호를 빈칸을 사이에 두고 출력한다. 만약 해가 두 가지 이상이면 그 중 한 가지만 출력한다. 다음 줄에 모든 역들의 응급대처시간 중 가장 긴 시간을 출력한다.
예제1
입력
12
133
342
457
564
676
785
846
235
797
91215
7102
10113
출력
812
13
출처
KOI 전국 2009 고3