给定一张 个点， 条边的无向图，点从 到 编号。
每条边可能有一个限速 ，表示走过这条边时必须把速度改为 。
特殊的，如果 ，表示没有限速，速度就不发生改变。
注意，这里的不改变是指沿用走过上一条边时的速度，而不是沿用初始速度。
每条边一定有一个长度 ，以 的速度开过花费的时间就是 。
初始你在 号点，速度为 ，现在需要求从 号点走到终点 所花费的最小总时间对应的路径。
数据保证无重边。
第一行三个整数 ，表示点数，边数和终点编号。
接下来 行，每行四个数 ，表示道路的起点，终点，限速和道路长度。
如果 ，表示这条道路没有速度限制。
一行若干个整数，表示一条从 到 的路径，需要满足花费的总时间最小。
数据保证只有一组最优解。
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
对于 的数据，，，，。
