题目描述

给定一张 $n$ 个点 $m$ 条边的无向图。你需要从点 $1$ 送外卖到点 $n$ 。路径的权值设计为从点 $1$ 到点 $n$ 的路径上最大边权和次大边权的和。你需要找到一条最优的路径，也就是路径的权值最小的那条路。输出最优路径的权值。

输入格式

第一行两个整数 $n,m\ (2\le n\le3\times10^5,\ max(1,n-1)\le m\le10^6)$，代表图的点数和边数。

接下来 $m$ 行每行输入三个整数 $u,v,w\ (1\le u,v\le n,\ 1\le w\le10^9)$，代表边的起点终点和边权。

图没有重边自环，并且图一定连通。

输出格式

一行一个整数代表答案

样例

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

5