题目描述

您现在在一张 $N$ 点 $M$ 边的无向图的点 $0$ 处，这 $N$ 个点编号为 $0$ 到 $N-1$。

每条边从 $A$ 连向 $B$，速度限制为 $V$，长度为 $L$，经过这条边的时间的算法如下：

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

其中 $V_\text{old}$ 为您经过的上一条边的 $V$ 的值，最开始 $V_\text{old}=70$。

如果 $V=0$，这条边的 $V$ 的值在计算完 $T$ 后更新为 $V_\text{old}$，$V_\text{old}$ 更新为 $V$。

您先在要从点 $0$ 到点 $D$，求一条从 $0$ 到 $D$ 的路径使得花的时间最少。

输入格式

第一行三个整数 $N,M,D$ 代表点数，边数和终点。
接下来 $M$ 行每行四个整数 $A,B,V,L$ 代表一条边。

输出格式

一行若干个整数代表花的时间最少的路径。

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

提示

样例说明

对于样例 $1$，输出这条路径花的时间最少，为 $2628$。

数据规模与约定

对于 $100\%$ 的数据，$2 \le M \le N \le 150$，$0 \le V,L \le 500$。

说明

翻译自 BalticOI 2002 Day1 A Speed Limits。