5339. 航班折扣（Flight Discount）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 你的任务是找到从Syrjälä到Metsälä的最低价飞行路线。你有一张折扣券，可以在路线中任意选择一段航班将其价格减半。但注意，这张券只能使用一次。 当你对价格为x的航班使用折扣券时，其价格将变为\lfloorx/2\rfloor（结果向下取整）。 ## 输入格式 第一行输入包含两个整数n和m，分别表示城市数量和航班数量。城市编号为1,2,\dots,n，其中1号城市是Syrjälä，n号城市是Metsälä。 接下来m行描述航班信息，每行包含三个整数a、b和c，分别表示航班起始城市、到达城市和机票价格。所有航班均为单向航线。 数据保证从Syrjälä到Metsälä一定存在可行路线。 ## 输出格式 输出一个整数，表示使用优惠券后从Syrjälä到Metsälä的最低总票价。 ## 输入输出样例 ### 输入 #1 ``` 3 4 1 2 3 2 3 1 1 3 7 2 1 5 ``` ### 输出 #1 ``` 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$