CSES1195 航班折扣
#CS1195. 航班折扣
航班折扣
题目背景
翻译自 CSES-1195 题。
题目描述
你的任务是找到从 Syrjälä 城市到 Metsälä 城市的最便宜航班路线。你有一个折扣券，使用它可以将路线上的某一段航班价格减半（只能使用一次）。
当你使用折扣券对一段价格为 x 的航班时，这段航班的价格变为 ⌊x2⌋\left\lfloor \frac{x}{2} \right\rfloor⌊2x⌋（向下取整到整数）。
输入格式
第一行包含两个整数 n 和 m：分别表示城市的数量和航班连接的数量。城市编号为 1,2,…,n1,2,…,n1,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
说明/提示