题目描述

图的最短路径

给定一个包含n个顶点和m条边的无向图，每条边都有一个正整数权重。请你找出从顶点1到顶点n的最短路径长度。如果顶点1和顶点n之间没有通路，则输出-1。

输入描述

第一行包含两个整数n和m，表示顶点数量和边的数量（1 ≤ n ≤ 100，1 ≤ m ≤ 1000）。 接下来m行，每行包含三个整数u、v、w，表示顶点u和顶点v之间有一条权重为w的边（1 ≤ u, v ≤ n，1 ≤ w ≤ 100）。

输出描述

输出从顶点1到顶点n的最短路径长度，如果没有通路则输出-1。

输入样例

5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1

输出样例

6

数据范围

1 ≤ n ≤ 100，1 ≤ m ≤ 1000，1 ≤ w ≤ 100