给定一个包含 $n$ 个节点（编号从 $1$ 到 $n$）和 $m$ 条边的无向图。每条边都有一个长度。图中不包含重边或自环。

Alice 和 Bob 正在玩一个游戏。每位玩家都需要选择一条从 $1$ 到 $n$ 的路径（不一定是简单路径）。这两条路径必须不同。

Alice 总是先手，她非常聪明，选择了一条从 $1$ 到 $n$ 的最短路径。现在轮到 Bob 了。Bob 想要选择一条从 $1$ 到 $n$ 的、与 Alice 的路径不同的最短路径。你的任务是求出这条路径的长度。

如果两条路径 $S$ 和 $T$ 的边数不同，或者存在某个整数 $i$ 使得 $S$ 的第 $i$ 条边与 $T$ 的第 $i$ 条边不同，则认为这两条路径是不同的。

输入格式

第一行包含两个整数：节点数 $n$ 和边数 $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$)。接下来的 $m$ 行，每行包含三个整数 $a, b$ 和 $w$，表示节点 $a$ 和节点 $b$ 之间有一条长度为 $w$ 的边 ($1 \le a, b \le n, 1 \le w \le 10^9$)。

保证至少存在一条从 $1$ 到 $n$ 的路径。

输出格式

输出一行，包含一个整数：Bob 所选路径的长度。

样例

样例输入 1

3 3
1 2 1
2 3 4
1 3 3

样例输出 1

5

样例输入 2

2 1
1 2 1

样例输出 2

3