#3245. 最快路线

题目描述

精明的小R每每开车出行总是喜欢走最快路线,而不是最短路线.很明显,每条道路的限速是小R需要考虑的关键问题.不过有一些限速标志丢失了,于是小R将不知道能开多快.不过有一个合理的方法是进入这段道路时不改变速度行驶.你的任务就是计算从小R家(0号路口)到D号路口的最快路线.

现在你得到了这个城市的地图,这个地图上的路都是单向的,而且对于两个路口A和B,最多只有一条道路从A到B.并且假设可以瞬间完成路口的转弯和加速.

输入格式

第一行是三个整数N,M,D(路口数目,道路数目,和目的地). 路口由0...N-1标号

接下来M行，每行描述一条道路:有四个整数A,B,V,L,(起始路口,到达路口,限速,长度) 如果V=0说明这段路的限速标志丢失.

开始时你位于0号路口,速度为70.

输出格式

仅仅一行,按顺序输出从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  

数据范围与提示

【数据范围】

30% N<=20

100% 2<=N<=150;0<=V<=500;1<=L<=500