Description
给你一个有向且边权全部非负的图，输出1到n的最短路。

Input
第一行两个自然数n(n<=100000)和m(m<=200000)，表示点数和边数。接下来m行，每行3个数a,b,l，其中1<=a,b<=n，l<=1000。

Output
仅一个整数，为1到n的最短路。如果无解，输出-1。
Sample Input
10 10
1 5 46
1 10 50
2 7 23
3 4 40
3 7 3
3 9 21
4 9 27
5 8 45
5 10 30
7 10 15

Sample Output
50
Hint
如果是练SPFA，过90分就可以了(不过如果你的SPFA可以过完，在下拜你为师……)。