Shortest Path on a Line
题意翻译
有一张有$N$个点，编号为$1 - N$ 的无向图
做$M$次操作 ， 每次操作给出三个正整数$L,R,C$，对于每对 $≥L$且$≤R$的整数对$(S,T)$,在$(S,T)$之间添加一条长度为$C$的边
完成操作后,找出操作后无向图的最短路。
题目描述
[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\ <\ t\ ≦\ R_i $ なる整数の組 $ (s,t) $ すべてに対し、頂点 $ s $ と頂点 $ t $ の間に長さ $ C_i $ の辺を追加する。
ただし、$ L_1,...,L_M $, $ R_1,...,R_M $, $ C_1,...,C_M $ はすべて入力で与えられます。
高橋君は最終的に得られたグラフ上で最短路問題を解きたいです。得られたグラフ上での頂点 $ 1 $ から頂点 $ N $ までの最短路の長さを求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ L_1 $ $ R_1 $ $ C_1 $ $ : $ $ L_M $ $ R_M $ $ C_M $
输出格式
頂点 $ 1 $ から頂点 $ N $ までの最短路の長さを出力せよ。 ただし、最短路が存在しない場合は `-1` を出力せよ。
输入输出样例
输入样例 #1
4 3
1 3 2
2 4 3
1 4 6输出样例 #1
5输入样例 #2
4 2
1 2 1
3 4 2输出样例 #2
-1输入样例 #3
10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3输出样例 #3
28说明
### 制約
- $ 2\ ≦\ N\ ≦\ 10^5 $
- $ 1\ ≦\ M\ ≦\ 10^5 $
- $ 1\ ≦\ L_i\ <\ R_i\ ≦\ N $
- $ 1\ ≦\ C_i\ ≦\ 10^9 $
### Sample Explanation 1
頂点 $ 1 $ と頂点 $ 2 $ の間に長さ $ 2 $ の辺があり、頂点 $ 2 $ と頂点 $ 4 $ の間に長さ $ 3 $ の辺があるので、頂点 $ 1 $ と頂点 $ 4 $ の間に長さ $ 5 $ のパスが存在します。