Score: $450$ points

问题陈述

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

你将执行 $M$ 次操作以向 $G$ 添加边。第 $i$ 次操作 $(1 \leq i \leq M)$ 如下：

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

执行完所有 $M$ 次操作后，确定 $G$ 是否连通。如果连通，找出 $G$ 的最小生成树中边的总权重。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a weighted undirected graph $G$ with $N$ vertices, numbered $1$ to $N$. Initially, $G$ has no edges.

You will perform $M$ operations to add edges to $G$. The $i$-th operation $(1 \leq i \leq M)$ is as follows:

• You are given a subset of vertices $S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace$ consisting of $K_i$ vertices. For every pair $u, v$ such that $u, v \in S_i$ and $u < v$, add an edge between vertices $u$ and $v$ with weight $C_i$.

After performing all $M$ operations, determine whether $G$ is connected. If it is, find the total weight of the edges in a minimum spanning tree of $G$.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

If $G$ is not connected after all $M$ operations, print -1. If $G$ is connected, print the total weight of the edges in a minimum spanning tree of $G$.

Sample Input 1

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

Sample Output 1

9

The left diagram shows $G$ after all $M$ operations, and the right diagram shows a minimum spanning tree of $G$ (the numbers next to the edges indicate their weights).

The total weight of the edges in the minimum spanning tree is $3 + 2 + 4 = 9$.

Sample Input 2

3 2
2 1
1 2
2 1
1 2

Sample Output 2

-1

$G$ is not connected even after all $M$ operations.

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