C. Unions - 水以下コンテスト

C - Unions

Ceylon

1024

100

点

問題文

$N$ 個の国 $1,2, \ldots,N$ があります。
また、複数の国で構成される同盟が $M$ 個あり、 $i$ 個目の同盟には $C_i$ 個の国 $(A_{i1}, A_{i2}, \ldots , A_{iC_i})$ が参加しています。

同じ同盟に属している国同士は直接行き来することができ、同盟 $i$ に属している国同士は $D_i$ 分で移動できます。
同じ同盟に属していない国同士は直接行き来することができません。

国 $k=2,3,\ldots,N$ について、
国 $1$ から国 $k$ へ移動するのにかかる時間の最小値を求めてください。国 $1$ から国 $k$ へ移動することができない場合は $-1$ を出力してください。

制約

$2 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$2 \leq C_i~~(1 \leq i \leq M)$
$\sum_{i=1}^M C_i \leq 10^5$
$1 \leq A_{ij} \leq N ~~(1 \leq i \leq N, 1 \leq j \leq C_i)$
$j \neq k \Rightarrow A_{ij} \neq A_{ik}$
$1 \leq D_i \leq 10^9~~(1, \leq i \leq N)$

部分点

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。

(20点) $C_i = 2~~(1 \leq i \leq M), ~~\sum_{i=1}^{M} C_i \leq 1000$
(30点) $\sum_{i=1}^{M} C_i \leq 1000$
(50点) 追加の制約なし

入力

入力は、以下の形式で標準入力から与えられる。

$N$ $M$
$C_1$ $C_2$ $\ldots$ $C_M$
$D_1$ $D_2$ $\ldots$ $D_M$
$A_{11}$ $A_{12}$ $\ldots$ $A_{1C_1}$
$A_{21}$ $A_{22}$ $\ldots$ $A_{2C_2}$
$\vdots$
$A_{M1}$ $A_{M2}$ $\ldots$ $A_{MC_M}$

出力

$N-1$ 行で、 $k$ 行目には国 $1$ から国 $k+1$ に移動するのにかかる時間の最小値(到達不可能な場合は $-1$ )を出力せよ。

入力例 1

7 7
2 2 2 2 2 2 2
4 3 2 5 3 5 7
1 2
1 5
2 3
2 5
3 4
4 5
4 6

出力例 1

例えば次のように移動することで、国 $1$ から国 $6$ へ $15$ 分で移動でき、これが最短となります。

国 $1$ から国 $5$ へ移動する(同盟 $2$ , $3$ 分)
国 $5$ から国 $4$ へ移動する(同盟 $6$ , $5$ 分)
国 $4$ から国 $6$ へ移動する(同盟 $7$ , $7$ 分)

また、国1から国7へは移動することができないため、6行目には-1を出力してください。
このサンプルは部分点1の制約を満たします。

入力例 2

20 11
10 3 4 2 2 3 5 2 4 5 3
83 45 92 24 94 22 52 23 79 72 49
3 4 5 9 10 11 12 13 18 20
6 9 3
5 7 9 11
5 12
1 10
7 2 16
6 9 10 15 14
1 13
6 13 15 17
8 7 12 4 15
2 8 19

出力例 2

このサンプルは部分点2の制約を満たします。