题目描述

Pigeland 的地铁系统非常先进。地铁系统由 $n$ 座车站构成，编号从 $1$ 到 $n$，还有 $k$ 条有向地铁线，编号从 $1$ 到 $k$。线路 $i$ 按顺序经过车站 $x_{i, 1}, x_{i, 2}, \cdots, x_{i, p_i}$，其中 $x_{i, j}$ 是线路 $i$ 经过的第 $j$ 座车站。搭乘线路 $i$ 从车站 $x_{i,j}$ 到车站 $x_{i,j+1}$ 需要花 $w_{i,j}$ 单位时间。

当多条线路经过同一车站时，乘客可以在线路之间换乘。若乘客目前位于线路 $x$ 上的一座车站，而线路 $y$ 也经过该车站，他/她就能花 $a_y \times b_x$ 单位时间从线路 $x$ 换乘到线路 $y$，其中 $a_y$ 和 $b_x$ 是线路 $y$ 和 $x$ 给定的参数。换乘后，乘客位于相同车站的线路 $y$ 中。

您将从车站 $1$ 出发。对所有 $2 \le s \le n$，求到达车站 $s$ 需要的最短时间。更具体地，您可以选择从车站 $1$ 的任意线路出发，出发时不消耗换乘时间。保证所有车站都能从车站 $1$ 到达。

输入格式

每个测试文件仅有一组测试数据。

第一行输入两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \times 10^5$，$1 \leq k \leq 2 \times 10^5$），表示车站的数量和地铁线的数量。

第二行输入 $k$ 个整数 $a_1, a_2, \cdots, a_k$（$1 \leq a_i \leq 10^6$）。

第三行输入 $k$ 个整数 $b_1, b_2, \cdots, b_k$（$1 \leq b_i \leq 10^6$）。

对于接下来 $k$ 行，第 $i$ 行首先输入一个整数 $p_i$（$2 \leq p_i \leq n$），表示线路 $i$ 经过的车站数。接下来输入 $(2p_i - 1)$ 个整数 $x_{i, 1}, w_{i, 1}, x_{i, 2}, \ldots, x_{i, p_i - 1}, w_{i, p_i - 1}, x_{i, p_i}$（$1 \leq x_{i,j} \leq n$，$1 \leq w_{i,j} \leq 10^9$），其中 $x_{i, j}$ 是线路 $i$ 经过的第 $j$ 座车站，$w_{i,j}$ 是搭乘线路 $i$ 从车站 $x_{i,j}$ 到车站 $x_{i,j+1}$ 的耗时。一条地铁线经过的车站互不相同。

保证 $\sum\limits_{i=1}^k (p_i - 1) \leq 2 \times 10^5$。

输出格式

输出一行 $(n - 1)$ 个由单个空格分隔的整数 $d_2, d_3, \cdots, d_n$，其中 $d_i$ 是从车站 $1$ 到车站 $i$ 的最短时间。

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

2 5 21 14 18

6 3
1 5 1
5 5 1
5 1 2 2 100 3 100 6 1 4
5 1 100 2 4 3 100 5 1 4
2 3 1 5

2 31 43 37 136