Description

In Pigeland, the subway system is quite advanced. It consists of $n$ sites, numbered from $1$ to $n$, and $k$ directed subway lines, numbered from $1$ to $k$. Subway line $i$ travels through sites $x_{i, 1}, x_{i, 2}, \cdots, x_{i, p_i}$ in order, where $x_{i, j}$ is the $j$-th site visited by line $i$. It takes $w_{i,j}$ units of time to travel from site $x_{i,j}$ to site $x_{i,j+1}$ on line $i$.

When multiple lines meet at the same site, passengers can transfer between lines. If a passenger is at a site on line $x$, while line $y$ also passes through this site, he/she can spend $a_y \times b_x$ units of time to transfer from line $x$ to line $y$, where $a_y$ and $b_x$ are given coefficients for lines $y$ and $x$. After transferring, the passenger is still at the same site, but on line $y$.

You start at site $1$. Find the minimum time needed to reach site $s$ for all $2 \le s \le n$. In particular, you can start by choosing any line at site $1$ with no transfer time cost. It is guaranteed that all sites are reachable from site $1$.

Input Format

There is only one test case in each test file.

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 2 \times 10^5$, $1 \leq k \leq 2 \times 10^5$), indicating the number of sites and the number of subway lines.

The second line contains $k$ integers $a_1, a_2, \cdots, a_k$ ($1 \leq a_i \leq 10^6$).

The third line contains $k$ integers $b_1, b_2, \cdots, b_k$ ($1 \leq b_i \leq 10^6$).

For the following $k$ lines, the $i$-th line first contains an integer $p_i$ ($2 \leq p_i \leq n$), indicating the number of sites line $i$ travels through. Then $(2p_i - 1)$ integers $x_{i, 1}, w_{i, 1}, x_{i, 2}, \ldots, x_{i, p_i - 1}, w_{i, p_i - 1}, x_{i, p_i}$ follow ($1 \leq x_{i,j} \leq n$, $1 \leq w_{i,j} \leq 10^9$), where $x_{i, j}$ is the $j$-th site visited by line $i$, and $w_{i,j}$ is the travel time from site $x_{i,j}$ to site $x_{i,j+1}$ on line $i$. The sites traveled through by a subway line are distinct.

It is guaranteed that $\sum\limits_{i=1}^k (p_i - 1) \leq 2 \times 10^5$.

Output Format

Output one line containing $(n - 1)$ integers $d_2, d_3, \cdots, d_n$ separated by a space, where $d_i$ is the minimum time cost from site $1$ to site $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