团连边

题目描述

给定一个有 $N$ 个顶点(编号为 $1$ 到 $N$)的带权无向图 $G$。初始时 $G$ 没有任何边。

你将执行 $M$ 次操作向 $G$ 中添加边。第 $i$ 次操作($1 \le i \le M$)如下:

给定一个由 $K_i$ 个顶点组成的顶点子集 $S_i = \lbrace A_{i,1}, A_{i,2}, \dots, A_{i,K_i} \rbrace$。 对于满足 $u, v \in S_i$ 且 $u \lt v$ 的每一对顶点 $u, v$,在顶点 $u$ 和 $v$ 之间添加一条权值为 $C_i$ 的边。

执行完所有 $M$ 次操作后,判断 $G$ 是否连通。若连通,求 $G$ 的最小生成树中边的总权值。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

如果执行完所有 $M$ 次操作后 $G$ 不连通,输出 $-1$。如果 $G$ 连通,输出 $G$ 的最小生成树中边的总权值。

样例

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

9

所有操作完成后的 $G$ 的一棵最小生成树中,边的总权值为 $3 + 2 + 4 = 9$。

3 2
2 1
1 2
2 1
1 2

-1

即使执行完所有 $M$ 次操作,$G$ 也不连通。

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

1202115217

数据范围

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