Description

给出一张无向带权图，求起点1到终点n的最短路

Format

Input

第一行有两个整数n, m; n表示顶点的个数，m表示边的条数。
接下来m行，每行有三个整数a, b, c； 表示a与b相连，a到b的距离为c。

Output

一个整数all,表示从1到n的最短路

Sample 1

Input

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

Output

5

Limitation

1s, 131072KiB for each test case.

Hint

对于30%的数据，1 <= n <= 100，1<=m<=1000, 0≤c≤1000；
对于70%的数据，1 <= n <= 2000,1<=m<=20000, 0≤c≤1000；
对于100%的数据，1 <= n <= 100000,1<=m<=100000, 0≤c≤1000。

Source

TYWZ