寒假里，小呆要去位于A市的皮球家拜年。小呆来到A市的车站，买了一张A市的地图，他发现这里的地形非常的复杂。A市的街道一共有N个路口，M条道路，每条道路连接着两个路口，并且有各自的长度。目前，小呆所在的车站位于编号为1的路口，而皮球家所在的路口编号为N，小呆准备打出租车去，当然，路程越小，付的钱就越少。问题摆在眼前：请帮助小呆寻找一条最短路径，使得他可以花最少的钱到达皮球家。

输入文件的第一行有两个整数N;M,(N<=1000<=M)分别代表路口数和街道数。以下有M行用以描述各个街道，每行有三个数字P1;P2;L,分别代表此街道起点编号，此街道终点编号以及此街道的长度。保证所给的数据可以构成连通图。

输出文件中只要求出现一行，一个整数，说明最短路径的长度(<=maxlongint)。

6 7
1 2 1
1 3 5
1 4 2
4 6 10
2 5 3
3 5 8
5 6 7

11