旅行老K

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

两个整数n,m

接下来有m行

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

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

3 2
1 2 1
2 3 1
4 2
1 2 1
2 3 1
4 2
1 2 1
2 4 1

2
-1
2