时空限制

1S/512M

题目描述

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

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

1. 蓄力：当 apiadu 处于某个城市时，他可以选择对下一条要走的边进行“蓄力”。如果他选择这么做，那么走完这条边所需的时间将变为原来的 2 倍。
2. 冲刺：在完成一次“蓄力”骑行并到达下一个城市后，他会立即获得“冲刺”状态。在这个状态下，他接下来要走的下一条边将不花费任何时间（时间为 0）。

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

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

格式

输入格式

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

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

输出格式

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

样例

样例输入 #1

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

样例输出 #1

30

数据规模

对于 $30\%$ 测试数据，$2 \le n \le 2 \times 10^5$，保证给出的图是一个树。

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