레이팅 미적용지하철 망이 있다. 이 지하철 망은 하나의 순환선과 이 순환선상의 역에 연결되는 지선들로 구성되어 있고, 각 지선은 트리 형태이다. 각 역에는 지선들이 없을 수도 있어서, 지하철이 순환선만으로 구성될 수도 있다. 모든 역은 1부터 \(N\)까지의 번호로 나타낸다. 아래 그림은 이러한 형태의 지하철 망의 예를 보여준다. 그림에서 정점은 지하철역을 나타내고, 간선은 두 역을 잇는 선로를 나타내며 간선상의 값은 선로를 지나는데 걸리는 시간을 나타낸다. 지하철 망의 역의 개수와 선로의 개수는 항상 같음에 유의하라.
지하철 사고 발생 시 응급치료를 위하여 2개의 역에 응급센터를 설치하기로 하였다. 각 역의 응급대처시간은 가까운 응급센터까지 가는데 걸리는 최단 시간이다. 모든 역들의 응급대처시간 중 가장 긴 시간이 최소가 되도록 2 개의 응급센터 설치 역을 구하는 프로그램을 작성하시오.
위의 그림에서 역 8과 역 12에 응급센터를 설치할 경우, 역 1에서부터 역 12까지의 응급대처시간은 각각 11, 13, 8, 6, 13, 11, 5, 0, 12, 7, 10, 0으로서 가장 긴 시간은 13이다. 또한, 두 응급센터를 어디에 설치하더라도, 모든 역들의 응급 대처시간 중 가장 긴 시간은 13보다 작아지지 않는다.
첫째 줄에 역의 개수(선로의 개수)인 \(N(3 \le N \le 50{,}000)\)이 주어진다. 다음 줄부터 \(N\)줄에 걸쳐 각 줄에 하나의 선로를 나타내는 세 개의 양의 정수 \(u\), \(v\), \(x\)가 주어진다. 여기서 \(u\), \(v\)는 선로를 통해 연결되는 두 역의 번호이고, \(x\)는 이 선로를 지나는데 걸리는 시간이다. 단, \(x\)는 1 이상 10,000 이하이다.
첫째 줄에 응급센터를 설치하는 두 역의 번호를 빈칸을 사이에 두고 출력한다. 만약 해가 두 가지 이상이면 그 중 한 가지만 출력한다. 다음 줄에 모든 역들의 응급대처시간 중 가장 긴 시간을 출력한다.
12
1 3 3
3 4 2
4 5 7
5 6 4
6 7 6
7 8 5
8 4 6
2 3 5
7 9 7
9 12 15
7 10 2
10 11 3
8 12
13
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2009 > 2차 대회 > 고등부 3번