운송 문제

문제 정보

    • 문제 ID
    • 시간 제한
    • 메모리 제한
    • 제출 횟수
    • 정답 횟수 (비율)
    • 출제자
    • 출처
    • 분류

문제

judge-attachments/0644ef7d68a0223bf7661c4c80fc9022/delivery.png

위 그림은 여러 개의 도시들과 각 도시들을 잇는 도로를 나타냅니다. 도로들 위에 쓰여 있는 숫자는 도로의 길이를 뜻합니다. 특정한 시작 도시에서부터 끝 도시까지 물품을 운송하고 싶습니다. 이 때 택할 수 있는 가장 짧은 경로의 길이를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 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

노트