A-path
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
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
