Description

You are now at node $0$ in an undirected graph with $N$ nodes and $M$ edges. The $N$ nodes are numbered from $0$ to $N-1$.

Each edge connects $A$ and $B$, with speed limit $V$ and length $L$. The time to pass this edge is computed as follows:

$$T=\begin{cases}\dfrac{L}{V}\ (V\ne 0)\\\dfrac{L}{V_\text{old}}\ (V=0)\end{cases}$$

Here, $V_\text{old}$ is the value of $V$ on the previous edge you passed. Initially, $V_\text{old}=70$.

If $V=0$, then after computing $T$, the value of $V$ on this edge is updated to $V_\text{old}$, and $V_\text{old}$ is updated to $V$.

You want to go from node $0$ to node $D$. Find a path from $0$ to $D$ that minimizes the total travel time.

Input Format

The first line contains three integers $N,M,D$, representing the number of nodes, the number of edges, and the destination node.
The next $M$ lines each contain four integers $A,B,V,L$, representing an edge.

Output Format

Output one line with several integers, representing a path with the minimum total travel time.

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

Sample Explanation

For sample $1$, the time spent on the output path is the smallest, which is $2628$.

Constraints

For $100\%$ of the testdata, $2 \le M \le N \le 150$, $0 \le V,L \le 500$.

Note

Translated from BalticOI 2002 Day1 A Speed Limits。

Translated by ChatGPT 5