该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

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

您将执行 $M$ 个操作以向 $G$ 添加边。第 $i(1 \leq i\leq M)$ 个操作如下:

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

在执行所有 $M$ 次操作之后，确定 $G$ 是否连接。如果是，则求 $G$ 的最小生成树中的边的总权重。

PS：简而言之，有 $M$ 组小团体，第 $i$ 组小团体内部所有点之间有权重为 $C_i$ 的边。

数据规模

$2\leq N\leq 2×10^5$

$1\leq M\leq 2×10^5$

$2\leq K_i\leq N$

$\sum_{i=1}^{m}K_i\leq 4×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$ 的最小生成树中的边的总权重。

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

9

• 123这个小团体内部有3的边
• 12这个小团体内部有2的边
• 134这个小团体内部有4的边

左图显示了所有 $M$ 个操作后的 $G$，右图显示了 $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