分数: 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