AT_nikkei2019_2_qual_d Shortest Path on a Line

[problemUrl]: https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d 一直線上に $ N $ 個の点があり、順に $ 1 $ から $ N $ までの番号がついています。 高橋君はこれらの点を頂点として無向グラフを作ることにしました。 はじめはグラフに辺はないですが、$ M $ 回の操作によって辺を追加します。 $ i $ 回目の操作では次のように辺を追加します。 - $ 1 $ 以上 $ N $ 以下の整数 $ L_i $, $ R_i $ 及び正整数 $ C_i $ を用いる。 $ L_i\ ≦\ s\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L_1 $ $ R_1 $ $ C_1 $ $ : $ $ L_M $ $ R_M $ $ C_M $

頂点 $ 1 $ から頂点 $ N $ までの最短路の長さを出力せよ。 ただし、最短路が存在しない場合は `-1` を出力せよ。

### 制約 - $ 2\ ≦\ N\ ≦\ 10^5 $ - $ 1\ ≦\ M\ ≦\ 10^5 $ - $ 1\ ≦\ L_i\