题目描述

小曲星是一位极限骑手，他正在参加一场穿越n个城市、经过m条双向道路的骑行挑战赛。城市编号为1到n，小曲星的起点在1号城市，终点在n号城市。

除了正常的骑行，小曲星还有一个可以无限次使用的特殊技巧"蓄力冲刺”，这个技巧分为两个连续的阶段:

1.蓄力:当小曲星处于某个城市时，他可以选择对下一条要走的边进行"蓄力"。如果他选择这么做，那么走完这条边所需的时间将变为原来的2倍。

2.冲刺:在完成一次“蓄力"骑行并到达下一个城市后，他会立即获得“冲刺“状态。在这个状态下，他接下来要走的下一条边将不花费任何时间(时间为0)。

完成一次“冲刺”后，小曲星会恢复正常状态。在正常状态下，他可以选择继续普通骑行，也可以再次选择发动“蓄力冲刺”技巧。

请你帮助小曲星计算，从1号城市到达n号城市，最少需要花费多少时间。

输入格式

第一行包含两个整数n,m，表示城市的数量和道路的数量。

接下来m行，每行包含三个整数u,v,w，表示城市u和城市v之间存在一条双向道路，通过它需要的时间为w。

输出格式

输出一个整数，表示从 1 号城市到达 n 号城市所需的最短时间。

4 4
1 2 10
2 3 100
3 4 10
1 4 125

30

数据规模与约定

对于30%的数据 , $2\leq n\leq 2*10^5$,保证给出的图是一个树.

对于100%的数据 $2\leq n \leq 2*10^5 , 1\leq m \leq 2*10^5 , 1\leq u,v \leq n , 1 \leq w \leq 10^9$ , 保证从 1 号点至少存在一条路径可以到达 n 号点。