이반은 다음 프로그래밍 대회가 열리는 곳까지 가는 교통비를 자기 돈으로 내야 한다. 가진 돈은 S 유로뿐이다. 그래서 이반은 대중교통 시간표와 요금을 미리 조사했다.
이반이 사는 마을을 1번, 대회가 열리는 마을을 N번, 도중에 지나갈 수 있는 나머지 마을을 2,3,…,N−1번이라고 한다. 이반이 찾은 버스 노선은 M개다. 각 노선은 마을 v와 마을 w를 잇고, 어느 방향으로 타든 t시간이 걸리며 요금은 한 번에 e유로다. 같은 두 마을을 잇는 버스가 여러 개 있을 수 있고, 그 버스의 소요 시간과 요금은 서로 다를 수 있다.
요금 합이 S 유로 이하인 1번 마을에서 N번 마을까지의 경로를 찾는 프로그램을 작성하시오. 그런 경로가 여러 개면 버스에 앉아 있는 시간의 합이 가장 작은 경로를 찾아야 한다.
버스를 한 번 탈 때마다 그 노선의 요금 e를 내고 시간 t를 쓴다. 같은 마을이나 같은 노선을 여러 번 지나가도 되며, 그때마다 요금과 시간을 다시 더한다.
N이 1이면 출발지가 곧 목적지이므로 소요 시간은 0이다.
cho.sh