旅行老K

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
25.00%(1/4)
Description:

最近青蛙都四处逛了,老K虽然是屌丝可是也按捺不住自己漂流的心,毅然决然的骑上了自己的汗血宝马(红色脚踏车),决定骑车去拉萨,但是百度地图极其不给力,导航导到了高速公路上,人家也不让上啊,于是心灰意冷的老K只好向身为程序员大佬的你求救,希望你能帮助他寻找到一条从工商大学到拉萨的路。假设现在给你了n个点,其中1号点表示工商,n号点是拉萨,给你m个三元组如下形式(u,v,w)分别表示u,v之间有一条长度为w的路,老K是个大懒鬼,所以他希望路尽可能短,请你帮帮他吧。

Input:

两个整数n,m

接下来有m行

u,v,w表示如上所述意义,其中1<=n,m<=20000,1<=u,v<=n,w<100000

Output:

输出从工商大学到拉萨的少路程,假如不存在则输出-1

Sample Input:
3 2
1 2 1
2 3 1
4 2
1 2 1
2 3 1
4 2
1 2 1
2 4 1
Sample Output:
2
-1
2

Submit