2360: 小呆打车
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：333
解决：123
题目描述
寒假里，小呆要去位于A市的皮球家拜年。小呆来到A市的车站，买了一张A市的地图，他发现这里的地形非常的复杂。A市的街道一共有N个路口，M条道路，每条道路连接着两个路口，并且有各自的长度。目前，小呆所在的车站位于编号为1的路口，而皮球家所在的路口编号为N，小呆准备打出租车去，当然，路程越小，付的钱就越少。问题摆在眼前：请帮助小呆寻找一条最短路径，使得他可以花最少的钱到达皮球家。
输入
第一行有两个整数N;M,(N<=1000<=M<=3500)分别代表路口数和街道数。以下有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