AT_abc364_f [ABC364F] Range Connect MST

有一个包含 $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$ - 所有输入的值均为整数 ### 样例解释 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$。 ### 样例解释 2 该图是不连通的。 由 ChatGPT 4.1 翻译