问题说明

Steve要从公司搬物品到家，东西非常重，而且只能走路。为了少走一些路，Steve麻烦Gold King做一个搬家方案。
Steve从公司到家的路上有N个路口，编号从1–N。每两个路口之间可能有一条路线，总共有M条路线，每一条路线都有其对应的长度，Steve从1号路口开始，要到达N号路口，Gold King陷入了沉思，这个搬家方案该怎么做才能让需要走的路距离最短，最短距离是多少。

输入格式

输入第一行是两个整数N和M，表示有N个路口，并且有M条路线。
接下来M行，每行包括3个整数A，B，C，分别为A号路口到B号路口，距离是C。

输出格式

输出一个整数结果，表示制定出来的方案最短距离值是多少。

样例输入1：
2 1
1 2 3
样例输入2：
3 3
1 2 5
2 3 5
3 1 2

样例输出1：
3
样例输出2：
2

提示

2<=N<=100
1<=M<=3500
1<=A,B<=N
1<=C<=1000

来源/分类

算法培训-20-最短路径