问题 H: 尽职的光光男神

问题 H: 尽职的光光男神

时间限制: 1 Sec  内存限制: 128 MB
提交: 11  解决: 4
[提交][状态][讨论版]

题目描述

随着STA新成员的加入,光光男神想着是不是让大家通过一次野餐或聚会来增进各自之间的感情。
现在问题来了,大家平时都说自己很忙,只能在周末抽出一天来聚餐,而男神想让大家去一个离学校较远的地方玩儿,所以男神必须想办法让大家能够在来回的路途上少花些时间。
现在已知有N个车站,我们学校所处的位置记为1号车站,而要去的地方在N号车站,现给出车站间的路径情况和这条路消耗的时间,求从学校到目标地点所需的最少时间。

输入

第一行两个整数 T和N,代表着有T条路径,N个车站。
第2~T+1行,每行分别有3个以空格隔开的整数,a、b、time,表示a号车站到b号车站间有一条要消耗time时长的路。T<=2000,N<=1000,1<=time<=100.

输出

从1号车站到N号车站所要消耗的最少时间。

样例输入

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

样例输出

90

提示


路径是双向的。



车站与车站之间可能不仅仅只有一条直接路径哦。



样例中,途径1,2,3,4是最短路径。


[提交][状态]