Mr. Ham 是一只在 USTC 非常勤奋的仓鼠，他总是利用周末送外卖来赚取更多的钱。

为了最大化他的配送效率，他想写一个程序来寻找最短路径。

具体来说，我们可以将 Mr. Ham 所在的合肥市看作一个具有 $n$ 个顶点和 $m$ 条边的无向图。每条边都有一个拥堵等级 $w$。Mr. Ham 从顶点 $1$ 出发，想要将外卖送到顶点 $n$。Mr. Ham 发现配送时间总是由路径上拥堵等级最高的两条边决定的。因此，Mr. Ham 将路径的长度定义为路径中拥堵等级最高的两条边的拥堵等级之和。当路径中只有一条边时，长度定义为该边的拥堵等级。

现在，Mr. Ham 想知道从顶点 $1$ 到顶点 $n$ 的最小路径长度。由于 Mr. Ham 不会编程，他把这个任务交给了你。

输入格式

第一行包含两个整数 $n$ ($2 \le n \le 3 \times 10^5$) 和 $m$ ($\max(1, n - 1) \le m \le 10^6$)，分别表示顶点数和边数。

接下来的 $m$ 行包含图的边，每行一条边。第 $i$ 行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9$)，表示一条拥堵等级为 $w$ 的边 $(u, v)$。

给定的图中没有自环或重边，且保证给定的图是连通的。

输出格式

输出一行，仅包含一个整数，表示从顶点 $1$ 到顶点 $n$ 的最小路径长度。

样例

输入 1

4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9

输出 1

5