P1028灵舵渡千屿（helm）

【题目背景】

在晨汐港备齐远航所需的物资后，Gioush 大队再度驶入特西荼亚海。暮色中的金白鱼群将众人引向岛屿密布的海域，Ehundategh 于是让 tfbz 接管船上的灵舵，带领船队穿过千屿之间的水道。

【题目描述】

特西荼亚海中共有 $n$ 座岛屿，岛屿之间共有 $m$ 条单向航道，每条航道都有一定的航行费用。为了让掌舵者能够在交错的水道间迅速作出选择，Ehundategh 预先为每座岛屿的所有出航航道规定了固定次序：若从岛屿 $x$ 出发的航道共有 $d_x$ 条，则它们依次编号为 $1\sim d_x$。

船上的灵舵档位用整数 $p$ 表示，其上限为 $k$。启航时，tfbz 将灵舵档位设为 $1$。在航行途中的任意时刻，他都可以按照以下方式调整灵舵档位：

• 若 $p<k$，则可以花费 $v_p$ 的费用，使 $p\leftarrow p+1$；
• 若 $p>1$，则可以花费 $w_p$ 的费用，使 $p\leftarrow p-1$。

当船位于岛屿 $x$，且当前灵舵档位为 $p$ 时，若从岛屿 $x$ 出发的第 $p$ 条航道通向岛屿 $y$，其航行费用为 $z$，则 tfbz 可以花费 $z$ 的费用，操纵船沿这条航道抵达岛屿 $y$。航行结束后，灵舵档位不会改变。特别地，若从岛屿 $x$ 出发的航道不足 $p$ 条，则船此时无法从岛屿 $x$ 出航，但 tfbz 仍然可以继续调整灵舵档位。

Gioush 大队最初位于岛屿 $1$。为了在真正深入群岛前准备好每一条可能的航线，tfbz 希望知道：从岛屿 $1$ 出发，抵达每一座岛屿所需的最小费用分别是多少。

【输入格式】

从文件 $\textbf{\textit{helm.in}}$ 中读入数据。

第一行三个正整数 $n,m,k$，分别表示岛屿数量、单向航道数量和灵舵档位的上限。

第二行包含 $k-1$ 个非负整数 $v_1,v_2,\ldots,v_{k-1}$，表示调高灵舵档位所需的费用。当 $k=1$ 时，该行为空。

第三行包含 $k-1$ 个非负整数 $w_2,w_3,\ldots,w_k$，表示调低灵舵档位所需的费用。当 $k=1$ 时，该行为空。

接下来 $n$ 行描述各座岛屿的出航航道。第 $i$ 行的第一个整数 $d_i$ 表示从岛屿 $i$ 出发的航道数量；接下来包含 $2d_i$ 个整数 $y_{i,1},z_{i,1},y_{i,2},z_{i,2},\ldots,y_{i,d_i},z_{i,d_i}$，其中 $y_{i,j}$ 和 $z_{i,j}$ 分别表示第 $j$ 条航道通向的岛屿及其航行费用。

【输出格式】

输出到文件 $\textbf{\textit{helm.out}}$ 中。

输出一行 $n$ 个整数，其中第 $i$ 个整数表示从岛屿 $1$ 抵达岛屿 $i$ 所需的最小费用。若无法抵达岛屿 $i$，则输出 $-1$。

【样例 1 输入】

15 6 322 431 143 2 5 3 1 4 251 3 262 1 2 4 17080

【样例 1 输出】

10 5 3 4 -1

【说明/提示】

【样例 1 解释】

岛屿 $1$ 是 Gioush 大队的起点，因此抵达它所需的费用为 $0$。

保持灵舵档位为 $1$，可以花费 $5$ 抵达岛屿 $2$；先花费 $2$ 将灵舵档位调为 $2$，再花费 $1$ 航行，可以抵达岛屿 $3$；沿同样的航线抵达岛屿 $3$ 后，继续选择它的第 $2$ 条出航航道，便可以再花费 $1$ 抵达岛屿 $4$。可以证明，这三种方案的费用均为最小值。岛屿 $5$ 无法抵达，因此输出 $-1$。

【样例 2】

见选手目录下的 $\textbf{\textit{helm/helm2.in}}$ 和 $\textbf{\textit{helm/helm2.ans}}$。

该组样例符合测试点 $1\sim 6$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{helm/helm3.in}}$ 和 $\textbf{\textit{helm/helm3.ans}}$。

该组样例符合测试点 $7\sim 9$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{helm/helm4.in}}$ 和 $\textbf{\textit{helm/helm4.ans}}$。

该组样例符合测试点 $10\sim 15$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{helm/helm5.in}}$ 和 $\textbf{\textit{helm/helm5.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证：$1\leq n,m\leq 3\times 10^5$，$1\leq k\leq 2.5\times 10^5$，$0\leq v_i,w_i\leq 10^9$，$0\leq d_i\leq k$，$\sum_{i=1}^{n}d_i=m$，$1\leq y_{i,j}\leq n$，$1\leq z_{i,j}\leq 10^9$。

特殊性质 A：所有调高或调低灵舵档位的费用均为 $0$。

特殊性质 B：至多存在 $10$ 座岛屿满足 $d_i\geq 10$。