8289: BZOJ4289:PA2012 Tax

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给出一个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

提示


题目来源

没有写明来源

加入题单

算法标签: