AT_past202112_i 直通エレベーター

[problemUrl]: https://atcoder.jp/contests/past202112-open/tasks/past202112_i $ 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 $ 階まで移動するために最短で何分かかるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $

答えの値を出力せよ。

### 制約 - $ 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} $ - 入力は全て整数である。 ### Sample Explanation 1 次のように移動するのが最適です。 - $ 1 $ 階から $ 2 $ 階まで階段を使って $ 1 $ 分で移動する。 - $ 2 $ 階から $ 5 $ 階まで $ 1 $ 台目のエレベーターを使って $ 1 $ 分で移動する。 - $ 5 $ 階から $ 4 $ 階まで階段を使って $ 1 $ 分で移動する。 - $ 4 $ 階から $ 10 $ 階まで $ 2 $ 台目のエレベーターを使って $ 3 $ 分で移動する。