You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个由$N$个顶点构成的带权无向图$G$。图$G$的每个顶点都被赋予了从$1$到$N$的编号。最初，图$G$中一条边都不存在。

现在，要通过进行$M$次操作来向图$G$中添加边。第$i$（$1\leq i\leq M$）次操作如下：

• 会给出一个由$K_i$个顶点构成的顶点部分集合$S_i = \{ A_{i,1}, A_{i,2}, \dots, A_{i,K_i} \}$。对于满足$u, v \in S_i$且$u < v$的所有$u$和$v$，在顶点$u$和顶点$v$之间添加一条权重为$C_i$的边。

请判断在进行完所有$M$次操作后，图$G$是否连通，如果连通，则求出包含在图$G$的最小生成树中的边的权重总和。

输入格式

第1行包含两个整数$N$和$M$。

接下来$M$行，第$i$行描述第$i$次操作。

第$i$行首先包含两个整数$K_i$和$C_i$，然后包含$K_i$个整数$A_{i,1}, A_{i,2}, \dots, A_{i,K_i}$。

输出格式

如果在进行完所有$M$次操作后图$G$不连通，则输出“-1”；如果连通，则输出图$G$的最小生成树中所包含边的权重总和。

输入输出样例 #1

输入 #1

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

输出 #1

9

输入输出样例 #2

输入 #2

3 2
2 1
1 2
2 1
1 2

输出 #2

-1

输入输出样例 #3

输入 #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

输出 #3

1202115217

说明/提示

数据范围

• $2\leq N\leq 2\times 10^5\$
• $1\leq M\leq 2\times 10^5$
• $ 2\leq K_i\leq N , \displaystyle\sum_{i = 1}^{M}K_i\leq 4\times 10^5 $
• $1\leq A_{i,1}<A_{i,2}<\cdots <A_{i,K_i}\leq N$
• $1\leq C_i\leq 10^9$
• 输入的所有值都是整数

样例1解释

左边的图表示在进行了全部(M)次操作之后的图(G)，右边的图表示其最小生成树中的一棵（写在边旁边的数字表示该边的权重）。最小生成树中所包含的边的权重总和为(3 + 2 + 4 = 9) 。