A시에는 개의 건물이 있다. 건물들은 개의 양방향 도로로 연결되어 있으며, 임의의 두 건물 사이에는 이동 경로가 정확히 하나 존재한다.
각 도로에는 이동 시간이 정해져 있다. 번 건물과 번 건물을 잇는 도로의 이동 시간이 라면, 어느 방향으로 이동하더라도 만큼의 시간이 걸린다.
가까운 미래에 A시 근처의 바다에 거대한 운석이 떨어져 쓰나미가 발생할 것으로 예상된다. 시장 앗리는 시민들이 최대한 빠르게 대피할 수 있도록, 건물 중 정확히 하나를 골라 그 자리에 대피소를 건설하려 한다.
번 건물에 대피소를 건설했을 때, 번 건물에서 다른 모든 건물까지의 최단 이동 시간 중 최댓값을 라고 하자. 즉, 대피소에서 가장 멀리 떨어진 건물까지 이동하는 데 필요한 시간이 이다.
앗리는 가 최소가 되도록 대피소의 위치를 정하려 한다.
가능한 의 최솟값과, 그 값을 만드는 건물의 번호를 구하여라. 그런 건물이 여러 개라면 번호가 가장 작은 건물을 출력한다.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 대피소를 건설하는 비용의 최솟값을 출력한다.
둘째 줄에 그 비용을 만드는 건물의 번호를 출력한다. 그런 건물이 여러 개라면 번호가 가장 작은 건물을 출력한다.
번 도로는 번 건물과 번 건물을 연결하며, 이 도로를 이동하는 데 만큼의 시간이 걸린다.
