F - Range Connect MST Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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 の無向辺を追加する

すべての操作を終えた後グラフは連結であるか判定し、連結である場合はこのグラフの最小全域木のコストを求めてください。

ただし、最小全域木とはコストが最小の全域木のことを指し、全域木のコストとは全域木に使われた辺のコストの和のことを指します。

制約

  • 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
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q

出力

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

入力例 1

4 3
1 2 2
1 3 4
2 4 5

出力例 1

22

以下の辺からなる全域木が最小全域木のひとつとなります。

  • 頂点 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 を出力します。

入力例 2

6 2
1 2 10
4 6 10

出力例 2

-1

グラフは非連結です。

入力例 3

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

出力例 3

199651870599998

Score : 500 points

Problem Statement

There is a graph with N + Q vertices, numbered 1, 2, \ldots, N + Q. Initially, the graph has no edges.

For this graph, perform the following operation for i = 1, 2, \ldots, Q in order:

  • For each integer j satisfying L_i \leq j \leq R_i, add an undirected edge with cost C_i between vertices N + i and j.

Determine if the graph is connected after all operations are completed. If it is connected, find the cost of a minimum spanning tree of the graph.

A minimum spanning tree is a spanning tree with the smallest possible cost, and the cost of a spanning tree is the sum of the costs of the edges used in the spanning tree.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q

Output

If the graph is connected, print the cost of a minimum spanning tree. Otherwise, print -1.

Sample Input 1

4 3
1 2 2
1 3 4
2 4 5

Sample Output 1

22

The following edges form a minimum spanning tree:

  • An edge with cost 2 connecting vertices 1 and 5
  • An edge with cost 2 connecting vertices 2 and 5
  • An edge with cost 4 connecting vertices 1 and 6
  • An edge with cost 4 connecting vertices 3 and 6
  • An edge with cost 5 connecting vertices 3 and 7
  • An edge with cost 5 connecting vertices 4 and 7

Since 2 + 2 + 4 + 4 + 5 + 5 = 22, print 22.

Sample Input 2

6 2
1 2 10
4 6 10

Sample Output 2

-1

The graph is disconnected.

Sample Input 3

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

Sample Output 3

199651870599998