AT_abc364_f [ABC364F] Range Connect MST

[problemUrl]: https://atcoder.jp/contests/abc364/tasks/abc364_f $ N\ +\ Q $ 頂点のグラフがあり、頂点には $ 1,\ 2,\ \ldots,\ N\ +\ Q $ の番号がついています。グラフにははじめ辺がありません。 このグラフに対して $ i\ =\ 1,\ 2,\ \ldots,\ Q $ の順に以下の操作を行います。 - $ L_i\ \leq\ j\ \leq\ R_i $ を満たす各整数 $ j $ について頂点 $ N\ +\ i $ と頂点 $ j $ の間にコスト $ C_i $ の無向辺を追加する すべての操作を終えた後グラフは連結であるか判定し、連結である場合はこのグラフの最小全域木のコストを求めてください。 ただし、最小全域木とはコストが最小の全域木のことを指し、全域木のコストとは全域木に使われた辺のコストの和のことを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ L_1 $ $ R_1 $ $ C_1 $ $ L_2 $ $ R_2 $ $ C_2 $ $ \vdots $ $ L_Q $ $ R_Q $ $ C_Q $

グラフが連結である場合は最小全域木のコストを出力せよ。そうでない場合は $ -1 $ を出力せよ。

### 制約 - $ 1\ \leq\ N,\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ - 入力される値はすべて整数 ### Sample Explanation 1 以下の辺からなる全域木が最小全域木のひとつとなります。 - 頂点 $ 1 $ と $ 5 $ を結ぶコスト $ 2 $ の辺 - 頂点 $ 2 $ と $ 5 $ を結ぶコスト $ 2 $ の辺 - 頂点 $ 1 $ と $ 6 $ を結ぶコスト $ 4 $ の辺 - 頂点 $ 3 $ と $ 6 $ を結ぶコスト $ 4 $ の辺 - 頂点 $ 3 $ と $ 7 $ を結ぶコスト $ 5 $ の辺 - 頂点 $ 4 $ と $ 7 $ を結ぶコスト $ 5 $ の辺 $ 2\ +\ 2\ +\ 4\ +\ 4\ +\ 5\ +\ 5\ =\ 22 $ であるため、$ 22 $ を出力します。 ### Sample Explanation 2 グラフは非連結です。