分数: 6 点
问题陈述
有一个 N- 层建筑,有楼梯和 M 直达电梯。 (这里,最低层称为 1-st 楼。)
使用楼梯,可以在 i-th 和 (i+1)任一方向的第 2 层 1 分钟,每 i \, (1 \leq i \leq N - 1).
此外,使用 i第一部电梯,可以在 A_i-th 和 B_i任一方向的第 2 层 C_i 分钟,每个 i \, (1 \leq i \leq M).
找出从 1-st 楼 N- 楼。
约束
- 2 \leq N \leq 10^{18}
- 1 \leq M \leq 10^5
- 1 \leq A_i \lt B_i \leq N
- 1 \leq C_i \leq 10^{18}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 C_1 \vdots A_M B_M C_M
输出
打印代表答案的值。
示例输入 1
10 2 2 5 1 4 10 3
示例输出 1
6
到达那里的最佳方式如下。
- 使用楼梯从 1-st 楼 2-nd 楼 1 分钟。
- 使用 1-st 电梯到达 2-二楼 5- 楼 1 分钟。
- 使用楼梯从 5至 1 楼 4- 楼 1 分钟。
- 使用 2-nd 电梯从 4至 1 楼 10- 楼 3 分钟。
示例输入 2
1000000000000000000 1 1 1000000000000000000 1000000000000000000
示例输出 2
999999999999999999