题目描述

给定一个由 $N$ 个点、$M$ 条边构成的带权无向图，请计算从点 $1$ 到点 $N$ 的最短路长度。

输入格式

第一行包含两个整数 $N, M$，分别表示点的数量和边的数量。

接下来 $M$ 行，每行包含三个正整数 $a_i, b_i, c_i$，表示点 $a_i$ 和点 $b_i$ 之间有一条长度为 $c_i$ 的无向边。

输出格式

输出一个整数，表示点 $1$ 到点 $N$ 的最短距离。

样例

4 4
1 2 1
2 3 1
3 4 1
2 4 1

2

提示

样例解释

图中存在重边和自环。从 $1$ 到 $4$ 的最短路为 $1 \to 2 \to 4$，总长度为 $1+1=2$。

数据范围

• $1 \le N \le 100000$
• $1 \le M \le 500000$
• $1 \le a_i, b_i \le N$
• $1 \le c_i \le 1000$
• 图中可能存在重边和自环，数据保证 $1$ 到 $N$ 有路径相连。