'공채는코테다'와 '백갤러(117.111)' 는 각자 다른 이유로 거대한 서울에 들어왔다.
현재 서울은 여러 개의 체육관(노드) 과 그 사이를 연결하는 도로(간선) 로 이루어져 있다.

각 도로는 이동하는 데 걸리는 시간(가중치) 이 존재하며, 모든 시간은 양의 정수이다.


어느 날,

  • 공채는코테다는 1번 체육관에서 출발하고

  • 백갤러(117.111)는 N번 체육관에 있다.


공채는코테다는 가능한 한 최단 시간 안에 백갤러(117.111)를 만나 체육관에서 우테코 이야기를 나누고 싶다.

현재 서울의 구조가 주어질 때,
1번 체육관에서 N번 체육관까지 이동하는 데 필요한 최소 시간을 구하라.