当前没有测试数据。

题目描述

给出一个图，起始点是$1$，结束点是$N$，边是双向的。求点$1$到点$N$的最短距离。哈哈，这就是标准的最短路径问题。

输入格式

第一行为两个整数$N$和$M$。$N$表示图中点的数目，$M$表示图中边的数目

下来$M$行，每行三个整数$x$，$y$，$c$表示点$x$到点$y$之间存在一条边长度为$c$。

输出格式

输出一行，一个整数，即为点1到点N的最短距离。

如果点1和点N不联通则输出-1。

样例 #1

样例输入 #1

2 1
1 2 3

样例输出 #1

3

样例 #2

样例输入 #2

3 3
1 2 5
2 3 5
3 1 2

样例输出 #2

2

样例 #3

样例输入 #3

6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 6 6
5 6 9

样例输出 #3

20

提示

$x≠y,1≤c≤10000$

$0≤M≤200000$

$1≤N≤10000$

• $N$的范围

$30\%：1≤n≤100$

$50\%：1≤n≤1000$

$100\%：1≤n≤10000$