응급센터
시간 제한1초메모리 제한128 MB
원형 라인에 나무 형태의 지선이 붙은 지하철 네트워크에서 두 역에 응급센터를 설치해 모든 역의 최소 거리 중 최댓값을 최소화하는 문제입니다.
문제
지하철망은 하나의 순환선과 그 순환선의 역들에 붙어 있는 지선들로 이루어져 있다. 각 지선은 트리 형태이며, 어떤 역에는 지선이 없을 수도 있다. 따라서 전체 지하철망이 순환선만으로 이루어질 수도 있다. 모든 역은 1번부터 N번까지 번호가 붙어 있고, 선로는 두 역을 연결하며 각 선로에는 지나가는 데 걸리는 시간이 주어진다. 이 지하철망에서는 역의 수와 선로의 수가 항상 같다.
사고가 났을 때 빠르게 응급 처치를 할 수 있도록 서로 다른 두 역에 응급센터를 설치하려고 한다. 한 역의 응급대처시간은 그 역에서 더 가까운 응급센터까지 가는 최단 시간이다. 모든 역의 응급대처시간 중 최댓값이 가능한 한 작아지도록, 응급센터를 설치할 두 역을 구하여라.
입력
첫째 줄에 역의 개수이자 선로의 개수인 N이 주어진다. (3 <= N <= 50,000)
다음 N개의 줄에는 선로 하나를 나타내는 세 양의 정수 u, v, x가 주어진다. 이는 u번 역과 v번 역이 선로로 직접 연결되어 있으며, 그 선로를 지나가는 데 x의 시간이 걸린다는 뜻이다. x는 1 이상 10,000 이하이다.
출력
첫째 줄에 응급센터를 설치할 서로 다른 두 역의 번호를 공백으로 구분하여 출력한다. 조건을 만족하는 답이 여러 개라면 그중 아무 것이나 출력해도 된다.
둘째 줄에는 모든 역의 응급대처시간 중 최댓값을 출력한다.