区间连边的最小生成树

题目描述

有一个顶点编号为 $1, 2, \ldots, N + Q$、共 $N + Q$ 个顶点的图。初始时,图中没有任何边。

对这个图,按顺序对 $i = 1, 2, \ldots, Q$ 执行以下操作:

对满足 $L_i \le j \le 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$。

样例

4 3
1 2 2
1 3 4
2 4 5

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$。

6 2
1 2 10
4 6 10

-1

图是不连通的。

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

199651870599998

数据范围

• $1 \le N, Q \le 2 \times 10^5$
• $1 \le L_i \le R_i \le N$
• $1 \le C_i \le 10^9$
• 所有输入值都是整数