You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。

你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两个路口，并且最多只有一块限速标志，位于路的起点。两地 $A$ 和 $B$，最多只有一条道路从 $A$ 连接到 $B$。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然，你的车速不能超过当前的速度限制。

输入格式

第一行是 $3$ 个整数 $N$，$M$ 和 $D$（$2\leq N\leq 150$，$1\leq M\leq 22500$）。$N$ 表示路口的数目，用 $0 \sim N-1$ 标记。$M$ 是道路的总数，$D$ 表示你的目的地。

接下来的 $M$ 行，每行描述一条道路，每行有 $4$ 个整数 $A$（$0\leq A<N$），$B$（$0\leq B<N$），$V$ （$0\leq V\leq 500$）和 $L$（$1\leq L\leq 500$），这条路是从 $A$ 到 $B$ 的，速度限制是 $V$，长度为 $L$。如果 $V$ 是 $0$，表示这条路的限速未知。

如果 $V$ 不为 $0$，则经过该路的时间 $T=\frac{L}{V}$。否则 $T=\frac{L}{V_{old}}$，$V_{old}$ 是你到达该路口前的速度。开始时你位于 $0$ 点，并且速度为 $70$。

输出格式

输出文件仅一行整数，表示从 $0$ 到 $D$ 经过的城市。

输出的顺序必须按照你经过这些城市的顺序，以 $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