Time Limit: 2 sec / Memory Limit: 1024 MB

问题陈述

给你一个加权无向图 $G$ ，有 $N$ 个顶点，编号为 $1$ 至 $N$ 。最初， $G$ 没有边。

您将执行 $M$ 次操作为 $G$ 添加边。 $i$ -th 操作 $(1 \leq i \leq M)$ 如下：

• 给你一个由 $K_i$ 个顶点组成的顶点子集 $S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace$ 。对于 $u, v \in S_i$ 和 $u < v$ 中的每一对 $u, v$ ，在顶点 $u$ 和 $v$ 之间添加一条边，权重为 $C_i$ 。

完成所有 $M$ 操作后，确定 $G$ 是否相连。如果是，求 $G$ 最小生成树中各条边的总权重。

限制因素

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $2 \leq K_i \leq N$
• $\sum_{i=1}^{M} K_i \leq 4 \times 10^5$
• $ 1\leq A_{i,1} < A_{i,2} < \dots < A_{i,K_i} \leq N $
• $1 \leq C_i \leq 10^9$
• 所有输入值均为整数。

输入

输入内容由标准输入法提供，格式如下

$N$ $M$ $K_1$ $C_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,K_1}$ $K_2$ $C_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,K_2}$ $\vdots$ $K_M$ $C_M$ $A_{M,1}$ $A_{M,2}$ $\dots$ $A_{M,K_M}$

输出

如果 $G$ 在进行所有 $M$ 操作后仍未连接，则打印 -1。如果 $G$ 连接，则打印 $G$ 最小生成树中各条边的总权重。

Sample Input 1

4 3
3 3
1 2 3
2 2
1 2
3 4
1 3 4

样本输出 1

9

左图显示的是经过所有 $M$ 运算后的 $G$ ，右图显示的是 $G$ 的最小生成树（边旁的数字表示其权重）。

最小生成树中各条边的总权重为 $3 + 2 + 4 = 9$ 。

Sample Input 2

3 2
2 1
1 2
2 1
1 2

输出示例 2

-1

即使执行了所有 $M$ 操作， $G$ 仍未连接。

Sample Input 3

10 5
6 158260522
1 3 6 8 9 10
10 877914575
1 2 3 4 5 6 7 8 9 10
4 602436426
2 6 7 9
6 24979445
2 3 4 5 8 10
4 861648772
2 4 8 9

Sample Output 3

1202115217