Description

In this busy society, we often do not choose the shortest road but the fastest route. While driving, the speed limit of each road becomes the key factor. Unfortunately, some speed-limit signs are missing, so you cannot know how fast you should drive. A defensible approach is to keep driving at your previous speed. Your task is to compute the fastest route between two places.

You are given road traffic information for a modern city. To simplify the problem, the map includes only intersections and roads. Each road is directed, connects exactly two intersections, and has at most one speed-limit sign located at the start of the road. For any two intersections $A$ and $B$, there is at most one road from $A$ to $B$. You may assume instantaneous acceleration and no congestion or similar factors. Of course, your speed cannot exceed the current speed limit.

Input Format

The first line contains 3 integers $N$, $M$, and $D$ ($2\leq N\leq 150$, $1\leq M\leq 22500$). $N$ is the number of intersections, labeled from 0 to $N-1$. $M$ is the total number of roads, and $D$ is your destination.

The next $M$ lines each describe one road, with 4 integers $A$ ($0\leq A<N$), $B$ ($0\leq B<N$), $V$ ($0\leq V\leq 500$), and $L$ ($1\leq L\leq 500$). This road goes from $A$ to $B$, its speed limit is $V$, and its length is $L$. If $V$ is $0$, the speed limit on this road is unknown.

If $V$ is not $0$, the travel time is $T=\frac{L}{V}$. Otherwise $T=\frac{L}{V_{old}}$, where $V_{old}$ is your speed upon arriving at the intersection before this road. Initially, you are at 0 with speed 70.

Output Format

Output a single line of integers: the sequence of intersections you pass from 0 to $D$, in order, starting with 0 and ending with $D$, separated by spaces. There is only one fastest route.

6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40

0 5 2 3 1

Hint

Translated by ChatGPT 5