속도 제한

운전할 때 우리는 보통 가장 짧은 경로보다 시간이 가장 적게 걸리는 경로에 관심이 있으므로, 각 도로의 속도 제한이 매우 중요하다. 그런데 일부 속도 제한 표지판이 사라졌다. 운전자는 표지판이 없으면 그 도로의 속도 제한을 알 수 없으므로, 표지판이 없는 도로를 지날 때는 그 직전까지 지키던 속도 제한을 그대로 유지한다고 보는 것이 합리적이다.

교차로와 일방통행 도로로 이루어진 도로망이 주어진다. 각 도로는 정확히 두 교차로를 잇고, 도로의 시작 지점에 최대 하나의 속도 제한 표지판이 있다. 임의의 두 교차로 A와 B에 대해 A에서 B로 가는 도로는 최대 하나만 존재한다. 가속은 즉시 이루어지고, 다른 차량의 영향은 없으며, 현재 속도 제한을 절대 초과하지 않는다고 가정한다. 출발 교차로에서 목적지 교차로까지 가장 빠른 경로를 구하여라.

첫째 줄에 세 정수 N, M, D가 주어진다. N (2 ≤ N ≤ 150)은 0부터 N-1까지 번호가 매겨진 교차로의 수, M은 도로의 수, D는 목적지 교차로의 번호이다. 다음 M개의 줄에는 각각 네 정수 A (0 ≤ A < N), B (0 ≤ B < N), V (0 ≤ V ≤ 500), L (1 ≤ L ≤ 500)이 주어지며, 이는 교차로 A에서 교차로 B로 가는 도로의 속도 제한이 V이고 길이가 L임을 뜻한다. V가 0이면 표지판이 없는 것이다. 한 도로를 지나는 데 걸리는 시간 T는 V ≠ 0이면 T = L / V이고, 그렇지 않으면 T = L / V_prev이다. 여기서 V_prev는 그 도로에 진입할 때 지키고 있던 속도 제한이다(나눗셈은 실수로 계산한다). 처음에 당신은 교차로 0에 있고, 처음 속도 제한은 70이다.

0에서 D까지 가장 빠른 경로에서 지나는 교차로들을, 지나는 순서 그대로 0으로 시작해 D로 끝나도록 한 줄에 공백 하나로 구분하여 출력한다. 가장 빠른 경로는 항상 유일하다(같은 최소 시간을 갖는 서로 다른 경로는 존재하지 않는다).

한 경로의 총 이동 시간은 각 도로에서의 L / V의 합이며, 표지판이 없는 도로에서는 가장 최근에 지키던 속도 제한을 그대로 사용한다.