Problem Description

There is a building with $ N $ floors, and it has stairs and $ M $ direct elevators installed.

Using the stairs, for any $i\ (1\ \leq\ i\ \leq\ N\ -\ 1)$, you can move bi-directionally between the $ i $th and $ i+1 $th floors in $ 1 $ minute.
Also, for each $i\ (1\ \leq\ i\ \leq\ M)$, using the $ i $th elevator, you can move bi-directionally between the $ A_i $th and $ B_i $th floors in $ C_i $ minutes.

Determine the minimum time required to move from the $ 1 $st floor to the $ N $th floor.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $\vdots$ $ A_M $ $ B_M $ $ C_M $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

10 2
2 5 1
4 10 3

Sample Output #1

6

Sample Input #2

1000000000000000000 1
1 1000000000000000000 1000000000000000000

Sample Output #2

999999999999999999

Notes/Hints

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 inputs are integers.

Sample Explanation 1

The optimal way to move is as follows:
- Move from the $ 1 $st floor to the $ 2 $nd floor using the stairs in $ 1 $ minute.
- Move from the $ 2 $nd floor to the $ 5 $th floor using the $ 1 $st elevator in $ 1 $ minute.
- Move from the $ 5 $th floor to the $ 4 $th floor using the stairs in $ 1 $ minute.
- Move from the $ 4 $th floor to the $ 10 $th floor using the $ 2 $nd elevator in $ 3 $ minutes.

见题面 Input 部分

见题面 Output 部分