[Baltic2002]limit 速度限制

在日常出行中，我们通常希望选择耗时最短的路线。驾车时，道路上的限速是决定行驶时间的关键因素，但有些道路的限速标志已经丢失。驶入没有限速标志的道路时，车辆将继续沿用此前的限速。

给定一张包含 $N$ 个路口和 $M$ 条道路记录的地图。路口编号为 $0$ 到 $N-1$。每条道路记录表示一条从路口 $A$ 到路口 $B$ 的单向道路，对于同一有序点对 $(A,B)$，至多存在一条道路。

假设车辆加速不需要时间，道路上不会发生拥堵，且车速不能超过当前限速。车辆始终以当前允许的最高速度行驶。开始时，车辆位于 $0$ 号路口，当前限速为 $70$。

请计算并输出从 $0$ 号路口到目标路口 $D$ 的唯一最快路线。

输入格式

第一行包含三个整数 $N$、$M$、$D$，分别表示路口数量、道路记录数量和目标路口编号。

接下来 $M$ 行，每行包含四个整数 $A$、$B$、$V$、$L$，表示一条从路口 $A$ 到路口 $B$、长度为 $L$ 的单向道路。

若 $V>0$，则车辆驶入该道路时，当前限速变为 $V$；若 $V=0$，则表示该处的限速标志缺失，车辆继续沿用此前的当前限速。

若驶入道路时的当前限速为 $S$，则通过该道路所需的时间为 $\frac{L}{S}$。

输出格式

输出从 $0$ 号路口到 $D$ 号路口的唯一最快路线，按照经过顺序输出所有路口的编号，相邻编号之间用一个空格分隔。

样例输入

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

数据范围

• $2\le N\le 150$；
• $0\le A,B<N$，且 $A\ne B$；
• $0\le V\le 500$，且 $V=0$ 或 $1\le V\le 500$；
• $0\le L\le 10^4$；
• $0\le D<N$，且 $D\ne 0$；
• 目标路口一定可达，且最快路线唯一。

来源与许可

本题为 Baltic 2002 试题「速度限制」，题面与测试数据整理自 BZOJ。

样例 1

输入

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