问题描述

在一个繁忙的城市中，有一张包含 $n$ 个地点和 $m$ 条道路的无向图。假设你是某个快递公司的配送员，你需要从城市的起点——地点 $1$ ，将一份重要的包裹送到城市的终点——地点 $n$ 。在这个城市里，每一条道路都有不同的拥堵程度，因此每一条道路的通行时间不同。

你的目标是找到从地点 $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