题目描述

给定一张 $n$ 个点，$m$ 条边的无向图，点从 $0$ 到 $n-1$ 编号。

每条边可能有一个限速 $s$，表示走过这条边时必须把速度改为 $s$。

特殊的，如果 $s=0$，表示没有限速，速度就不发生改变。

注意，这里的不改变是指沿用走过上一条边时的速度，而不是沿用初始速度。

每条边一定有一个长度 $l$，以 $v$ 的速度开过花费的时间就是 $\frac{l}{v}$。

初始你在 $0$ 号点，速度为 $70$，现在需要求从 $0$ 号点走到终点 $d$ 所花费的最小总时间对应的路径。

数据保证无重边。

输入格式

第一行三个整数 $n,m,d$，表示点数，边数和终点编号。

接下来 $m$ 行，每行四个数 $u,v,s,l$，表示道路的起点，终点，限速和道路长度。

如果 $s=0$，表示这条道路没有速度限制。

输出格式

一行若干个整数，表示一条从 $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

数据规模与约定

对于 $100\%$ 的数据，$2\leq n\leq150$，$0\leq m\leq\frac{n·(n+1)}{2}$，$0\leq u,v,d<n$，$0\leq s,l\leq500$。