4289 - PA2012 Tax

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

Input

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

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

Output

一行一个数，表示答案。

Examples

Input

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

Output

12

Hint

n<\leq 10^5,m\leq 2\times 10^5,c\leq 10^6

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题