운송 문제
문제 정보
문제
위 그림은 여러 개의 도시들과 각 도시들을 잇는 도로를 나타냅니다. 도로들 위에 쓰여 있는 숫자는 도로의 길이를 뜻합니다. 특정한 시작 도시에서부터 끝 도시까지 물품을 운송하고 싶습니다. 이 때 택할 수 있는 가장 짧은 경로의 길이를 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어집니다. 각 테스트 케이스의 첫 줄에는 도시의 수 N (<= 10000) 과 도로의 수 M (<= 20000) 이 주어집니다. 각 도시는 0 부터 N-1 까지의 번호로 표현됩니다. 그 후 줄에 각 3개의 음이 아닌 정수로 각 도로의 정보가 주어집니다. 도로의 정보는 a b c 로 표현되며, 이 때 이 도로는 a 번과 b 번 도시 사이를 이으며 길이는 c 입니다. 모든 도로는 양방향 통행이 가능합니다.
시작 도시는 항상 0 번, 끝 도시는 항상 N-1 번이라고 가정하며, 이와 같은 경로는 언제나 존재한다고 가정합니다.
출력
각 테스트 케이스마다 가장 짧은 경로의 길이를 출력합니다.
예제 입력
1 7 14 0 1 3 0 2 10 0 3 9 3 4 4 3 5 16 3 1 12 1 2 4 1 2 10 1 4 3 1 5 10 5 4 9 4 6 4 5 6 16 2 6 30
예제 출력
10
노트