求最短路

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在一个无向图中,求1和n两个顶点之间的最短路。

Input

多组测试数据,对于每组测试数据,第1行输入正整数n(1 <= n <= 1000)、m,表示n个顶点(编号从1开始)和m条边。之后m行每行输入u(1 <= u <= n)、v(1 <= v <= n)、w(1 <= w <= 100),表示在顶点u和顶点v之间存在无向边,且权值为w。

Output

对于每组测试数据,若存在最短路则输出最短路径的权值和,若不存在最短路则输出-1。

Sample Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

Sample Output

90

Hint

Source

xry-fhf