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

Description

给定一个初始为空的 $N$ 个顶点的无向图（顶点编号为 $1$ 到 $N$）。你需要执行 $M$ 次操作来添加边。第 $i$ 次操作如下：

给定一个顶点子集 $S_i = {A_{i,1}, A_{i,2}, \dots, A_{i,K_i}}$ 和一个权值 $C_i$。

对于所有 $u, v \in S_i$ 且 $u < v$，在顶点 $u$ 和 $v$ 之间添加一条权值为 $C_i$ 的边。

完成所有操作后，判断图是否连通。如果连通，求出其最小生成树的边权和；否则输出 $-1$。

Format

Input

第一行：$N$ 和 $M$（$2 \leq N \leq 2 \times 10^5$，$1 \leq M \leq 2 \times 10^5$）。

接下来 $M$ 组数据，每组格式为：

第一行：$K_i$ 和 $C_i$（$2 \leq K_i \leq N$，$1 \leq C_i \leq 10^9$）。

第二行：$K_i$ 个严格递增的整数 $A_{i,1}, A_{i,2}, \dots, A_{i,K_i}$（$1 \leq A_{i,j} \leq N$）。

保证所有 $K_i$ 的总和不超过 $4 \times 10^5$。

Output

如果图连通，输出 MST 的边权和；否则输出 $-1$。

Samples

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

9

操作后图的边权分布：

$1-2$：权值 $2$ 和 $3$（取最小 $2$）。

$1-3$：权值 $3$。

$2-3$：权值 $3$。

$1-4$：权值 $4$。

$3-4$：权值 $4$。

MST 包含边 $1-2$（$2$）、$1-3$（$3$）、$3-4$（$4$），总权值为 $9$。