链接: https://cses.fi/problemset/task/1197

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你的任务是找出从 Syrjälä 到 Metsälä 的最低价格飞行路线。你有一张折扣券，使用它可以使路线上任意一趟航班的价格减半。不过，折扣券只能使用一次。

当你对价格为 $x$ 的航班使用折扣券时，其价格变为 $\lfloor x/2 \rfloor$（向下取整为整数）。

输入

第一行输入包含两个整数 $n$ 和 $m$：城市数量和航班连接数。城市编号为 $1,2,\ldots,n$。城市 1 是 Syrjälä，城市 $n$ 是 Metsälä。

之后有 $m$ 行描述航班。每行包含三个整数 $a$、$b$ 和 $c$：航班从城市 $a$ 出发，抵达城市 $b$，价格为 $c$。每个航班都是单向的。

你可以假设总能从 Syrjälä 到达 Metsälä。

输出

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

数据范围

$2 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$ $1 \le c \le 10^9$

样例输入

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

样例输出

2