#P18212. Subway

Subway

Subway

Pigeland 有一个先进的地铁系统,共有 nn 个站点,编号为 11 到 nn,以及 kk 条有向地铁线路,编号为 11 到 kk。

第 ii 条线路依次经过站点 xi,1,xi,2,…,xi,pix_{i,1},x_{i,2},\ldots,x_{i,p_i}。沿该线路从 xi,jx_{i,j} 到 xi,j+1x_{i,j+1} 需要 wi,jw_{i,j} 单位时间。

如果多条线路经过同一站点,乘客可以换乘。当乘客位于线路 xx 上,而线路 yy 也经过当前站点时,可以花费

ay×bxa_y\times b_x

单位时间,从线路 xx 换到线路 yy。换乘后,乘客仍位于同一站点,但所在线路变为 yy。ai,bia_i,b_i 是每条线路给定的系数。

你从站点 11 出发,最初可以免费选择任何经过站点 11 的线路。对于每个 2≤s≤n2\le s\le n,求到达站点 ss 的最短时间。

保证从站点 11 能够到达所有站点。

输入格式

每个输入文件只有一组测试数据。

第一行两个整数 n,kn,k,满足 2≤n≤2×1052\le n\le2\times10^5,1≤k≤2×1051\le k\le2\times10^5,分别表示站点数和线路数。

第二行 kk 个整数 a1,a2,…,aka_1,a_2,\ldots,a_k;第三行 kk 个整数 b1,b2,…,bkb_1,b_2,\ldots,b_k。它们均满足 1≤ai,bi≤1061\le a_i,b_i\le10^6。

接下来 kk 行。第 ii 行首先给出整数 pip_i(2≤pi≤n2\le p_i\le n),然后按以下顺序给出 2pi−12p_i-1 个整数:

$$x_{i,1},w_{i,1},x_{i,2},w_{i,2},\ldots,x_{i,p_i-1},w_{i,p_i-1},x_{i,p_i}.$$

其中 1≤xi,j≤n1\le x_{i,j}\le n,1≤wi,j≤1091\le w_{i,j}\le10^9。同一条线路经过的站点互不相同。 不同线路之间可以经过相同站点。

保证

∑i=1k(pi−1)≤2×105.\sum_{i=1}^{k}(p_i-1)\le2\times10^5.

输出格式

输出一行 n−1n-1 个由空格分隔的整数 d2,d3,…,dnd_2,d_3,\ldots,d_n,其中 did_i 是从站点 11 到站点 ii 的最短时间。

样例 1

输入:

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

样例 2

输入:

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