在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的 。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候却是非常累的!所以现在
他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
第一行两个整数 N, M 。 N 表示成都的大街上有几个路口,标记为 1 的路口是商店的所在地,标号为 N 的路口是赛场所在地, M则表示在成都都有那几条陆。 接下来M行,每行包括3个整数A,B,C。 表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路 如果不存在n前往1的路径则输出-1
输出一行,表示工作人员从商店走到赛场的最短时间。
样例输入 1
复制2 1 1 2 3
2 1 1 2 3
样例输出 1
复制3
3
样例输入 2
复制3 3 1 2 5 2 3 5 3 1 2
3 3 1 2 5 2 3 5 3 1 2
样例输出 2
复制10
10
N<= 100
M <= 10000