Flight Discount

题目描述

你的任务是找到从 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ä 的最便宜路线的价格。

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

2

提示

$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$

标签: CSES1195|图论

来源

CSES1195|图论