I - Direct Elevator Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

N 階建てのビルがあり、階段と M 台の直通エレベーターが設置されています。

階段を用いると、任意の i \, (1 \leq i \leq N - 1) について、i 階と i+1 階の間を双方向に 1 分で移動することができます。
また、各 i \, (1 \leq i \leq M) について、i 台目のエレベーターを用いると、A_i 階と B_i 階の間を双方向に C_i 分で移動することができます。

1 階から 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 階から 2 階まで階段を使って 1 分で移動する。
  • 2 階から 5 階まで 1 台目のエレベーターを使って 1 分で移動する。
  • 5 階から 4 階まで階段を使って 1 分で移動する。
  • 4 階から 10 階まで 2 台目のエレベーターを使って 3 分で移動する。

入力例 2

1000000000000000000 1
1 1000000000000000000 1000000000000000000

出力例 2

999999999999999999

Score : 6 points

Problem Statement

There is an N-story building, with stairs and M direct elevators. (Here, the lowest floor is called the 1-st floor.)

Using stairs, it is possible to travel between the i-th and (i+1)-th floors in either direction in 1 minute, for every i \, (1 \leq i \leq N - 1).
Additionally, using the i-th elevator, it is possible to travel between the A_i-th and B_i-th floors in either direction in C_i minutes, for each i \, (1 \leq i \leq M).

Find the minimum number of minutes needed to get from the 1-st floor to the N-th floor.

Constraints

  • 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}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

Output

Print the value representing the answer.

Sample Input 1

10 2
2 5 1
4 10 3

Sample Output 1

6

The optimal way to get there is as follows.

  • Use stairs to get from the 1-st floor to the 2-nd floor in 1 minute.
  • Use the 1-st elevator to get from the 2-nd floor to the 5-th floor in 1 minute.
  • Use stairs to get from the 5-th floor to the 4-th floor in 1 minute.
  • Use the 2-nd elevator to get from the 4-th floor to the 10-th floor in 3 minutes.

Sample Input 2

1000000000000000000 1
1 1000000000000000000 1000000000000000000

Sample Output 2

999999999999999999