지하철 망이 있다.

이 지하철 망은 하나의 순환선과 이 순환선상의 역에 연결되는 지선들로 구성되어 있고, 각 지선은 트리 형태이다. 각 역에는 지선들이 없을 수도 있어서, 지하철이 순환선 만으로 구성될 수도 있다. 모든 역은 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 이하이다.

출력

• 첫째 줄에 응급센터를 설치하는 두 역의 번호를 빈칸을 사이에 두고 출력한다. 만 약 해가 두 가지 이상이면 그 중 한 가지 만 출력한다.
• 다음 줄에 모든 역들의 응급대처시간 중 가장 긴 시간을 출력한다.

입출력 예

입력

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

출처: 제26회 한국정보올림피아드 (2009.7.17) 고등부 문제 3