시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 42 | 29 | 27 | 81.818% |
JOI-kun is living in a city with N stations. The stations are numbered from 1 to N. There are M railways numbered from 1 to M. The railway i (1 ≤ i ≤ M) connects the station Ai and the station Bi in both directions, and the fare is Ci yen.
JOI-kun is living near the station S, and goes to the IOI high school near the station T. He is planning to buy a commuter pass connecting these two stations. When he buys a commuter pass, he needs to choose a route between the station S and the station T with minimum cost. Using this commuter pass, he can take any railways contained in a chosen route in any directions without additional costs.
JOI-kun often goes to bookstores near the station U and the station V. Therefore, he wants to buy a commuter pass so that the cost from the station U to the station V is minimized.
When he moves from the station U to the station V, he first choose a route from the station U to the station V. Then the fare he has to pay is
The sum of the above fare is the cost from the station U to the station V.
He wants to know the minimum cost from the station U to the station V if he chooses a route appropriately when he buys a commuter pass.
Write a program which calculates the minimum cost from the station U to the station V if he chooses a route appropriately when he buys a commuter pass.
Read the following data from the standard input.
All input data satisfy the following conditions.
Write one line to the standard output. The output should contain the minimum cost from the station U to the station V if he chooses a route appropriately when he buys a commuter pass.
6 6 1 6 1 4 1 2 1 2 3 1 3 5 1 2 4 3 4 5 2 5 6 1
2
6 5 1 2 3 6 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000
3000000000
8 8 5 7 6 8 1 2 2 2 3 3 3 4 4 1 4 1 1 5 5 2 6 6 3 7 7 4 8 8
15
5 5 1 5 2 3 1 2 1 2 3 10 2 4 10 3 5 10 4 5 10
0
10 15 6 8 7 9 2 7 12 8 10 17 1 3 1 3 8 14 5 7 15 2 3 7 1 10 14 3 6 12 1 5 10 8 9 1 2 9 7 1 4 1 1 8 1 2 4 7 5 6 16
19
In this sample input 1, there is only one route JOI-kun can choose when he buys a commuter pass: Station 1 → Station 2 → Station 3 → Station 5 → Station 6.
In order to minimize the cost from the station 1 to the station 4, he chooses the following route: Station 1 → Station 2 → Station 3 → Station 5 → Station 4. When he chooses this route, the fare he has to pay is
Hence the total cost is 2 yen.
In this sample input 2, JOI-kun does not use the commuter pass when he moves from the station 3 to the station 6.