[BalticOI 2002 Day1] Speed Limits

您现在在一张 $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](https://boi.cses.fi/files/boi2002_day1.pdf)。