← 返回题目列表

AtCoder · past202112_i

I. 直达电梯

中文机器翻译题面 查看原题

分数: 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