题目描述

给出一个 $n$ 个点 $m$ 条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点 $1$ 到点 $n$ 的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。

输入格式

第一行两个数 $n,m$，分别表示点数和边数。

接下来 $m$ 行，每行三个数 $a,b,c$，表示 $a,b$ 之间存在一条长度为 $c$ 的边。

输出格式

一行一个数，表示答案。

4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8

12

提示

$1\leq n\leq 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq c\leq 10^6$。