#1591 운송 문제

69  10 s   128 MB  

Description

 

 

 

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

 

Input

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어집니다. 각 테스트 케이스의 첫 줄에는 도시의 수 N (<= 10000) 과 도로의 수 M (<= 20000) 이 주어집니다. 각 도시는 0 부터 N-1 까지의 번호로 표현됩니다. 그 후 줄에 각 3개의 정수로 각 도로의 정보가 주어집니다. 도로의 정보는 a b c 로 표현되며, 이 때 이 도로는 a 번과 b 번 도시 사이를 이으며 길이는 c 입니다. 모든 도로는 양방향 통행이 가능합니다.

시작 도시는 항상 0 번, 끝 도시는 항상 N-1 번이라고 가정하며, 이와 같은 경로는 언제나 존재한다고 가정합니다.

 

 

 

Output

각 테스트 케이스마다 가장 짧은 경로의 길이를 출력합니다.

 

Sample Input

Sample Output

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