A30879.【算法】Gold King的搬家方案

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。

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

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