지하철 망이 있다. 이 지하철 망은 하나의 순환선과 이 순환선상의 역에 연결되는 지선들로 구성되어 있고, 각 지선은 트리 형태이다. 각 역에는 지선들이 없을 수도 있어서, 지하철이 순환선만으로 구성될 수도 있다. 모든 역은 1부터 N까지의 번호로 나타낸다. 아래 그림은 이러한 형태의 지하철 망의 예를 보여준다. 그림에서 정점은 지하철역을 나타내고, 간선은 두 역을 잇는 선로를 나타내며 간선상의 값은 선로를 지나는데 걸리는 시간을 나타낸다. 지하철 망의 역의 개수와 선로의 개수는 항상 같음에 유의하라.

지하철 사고 발생 시 응급치료를 위하여 2개의 역에 응급센터를 설치하기로 하였다. 각 역의 응급대처시간은 가까운 응급센터까지 가는데 걸리는 최단 시간이다. 모든 역들의 응급대처시간 중 가장 긴 시간이 최소가 되도록 2 개의 응급센터 설치 역을 구하는 프로그램을 작성하시오.

위의 그림에서 역 8과 역 12에 응급센터를 설치할 경우, 역 1에서부터 역 12까지의 응급대처시간은 각각 11, 13, 8, 6, 13, 11, 5, 0, 12, 7, 10, 0으로서 가장 긴 시간은 13이다. 또한, 두 응급센터를 어디에 설치하더라도, 모든 역들의 응급 대처시간 중 가장 긴 시간은 13보다 작아지지 않는다.