E - Clique Connect Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450

問題文

N 頂点からなる重み付き無向グラフ G があります。 G の各頂点には 1 から N までの番号が付けられています。 最初、G には辺が 1 本も存在しません。

今から、M 回の操作を行うことによって G に辺を追加していきます。 i\ (1\leq i\leq M) 回目の操作は以下の通りです。

  • K_i 頂点からなる頂点の部分集合 S_i=\lbrace A_{i,1},A_{i,2},\dots,A_{i,K_i}\rbrace が与えられる。 u,v\in S_i かつ u<v を満たす全ての u,v について、頂点 u と頂点 v の間に重み C_i の辺を追加する。

M 回の操作を全て行ったとき G が連結になるか判定し、連結になるならば G の最小全域木に含まれる辺の重みの総和を求めてください。

制約

  • 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} < \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}

出力

M 回の操作を全て行ったとき G が連結にならないならば -1 を、連結になるならば G の最小全域木に含まれる辺の重みの総和を出力せよ。


入力例 1

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

出力例 1

9

左の図は M 回の操作を全て行ったあとの G を、右の図はその最小全域木の 1 つを表しています(辺の横に書かれた数はその辺の重みを示します)。

最小全域木に含まれる辺の重みの総和は 3+2+4=9 です。


入力例 2

3 2
2 1
1 2
2 1
1 2

出力例 2

-1

M 回の操作を全て行っても G は連結になりません。


入力例 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

Score: 450 points

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