该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你的任务是找到从 Syrjälä 城市到 Metsälä 城市的最便宜航班路线。你有一个折扣券，使用它可以将路线上的某一段航班价格减半（只能使用一次）。

当你使用折扣券对一段价格为 $x$ 的航班时，这段航班的价格变为 $\left\lfloor \frac{x}{2} \right\rfloor$（向下取整到整数）。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示城市的数量和航班连接的数量。城市编号为 $1,2,…,n$，其中城市 $1$ 是 Syrjälä，城市 $n$ 是 Metsälä。

接下来有 $m$ 行，每行描述一个航班，包含三个整数 $a$, $b$ 和 $c$：表示一段从城市 $a$ 到城市 $b$ 的航班，航班的价格为 $c$。每个航班是单向的。

你可以假设从 Syrjälä 到 Metsälä 一定是可达的。

输出格式

输出一个整数：表示从 Syrjälä 到 Metsälä 的最便宜路线的价格。

样例

3 4
1 2 3
2 3 1
1 3 7
2 1 5

2

说明/提示

$2 \leq n \leq 10^5$；

$1 \leq m \leq 2 \cdot 10^5$；

$1 \leq a,b \leq n$；

$1 \le c \le 10^9$。