4515 - 第十课:最短路x

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

N<=100000

M<=200000

输入

 

输出

 

样例

输入

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

输出

12
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题