← 返回题目列表

AtCoder · abc364_f

I. 范围连接 MST

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有一个图表 N + Q 顶点,编号 1, 2, \ldots, N + Q。最初,该图没有边。

对于该图,请执行以下操作: i = 1, 2, \ldots, Q 按顺序:

  • 对于每个整数 j 满意 L_i \leq j \leq R_i,添加一条带有成本的无向边 C_i 顶点之间 N + i 和 j.

所有操作完成后判断图形是否连通。如果连通,求图的最小生成树的成本。

最小生成树是具有最小可能成本的生成树,生成树的成本是生成树中使用的边的成本之和。

约束

  • 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

以下边形成最小生成树:

  • 成本优势 2 连接顶点 1 和 5
  • 成本优势 2 连接顶点 2 和 5
  • 成本优势 4 连接顶点 1 和 6
  • 成本优势 4 连接顶点 3 和 6
  • 成本优势 5 连接顶点 3 和 7
  • 成本优势 5 连接顶点 4 和 7

自从 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