#P18212. Subway
Subway
Subway
Pigeland 有一个先进的地铁系统,共有 个站点,编号为 到 ,以及 条有向地铁线路,编号为 到 。
第 条线路依次经过站点 。沿该线路从 到 需要 单位时间。
如果多条线路经过同一站点,乘客可以换乘。当乘客位于线路 上,而线路 也经过当前站点时,可以花费
单位时间,从线路 换到线路 。换乘后,乘客仍位于同一站点,但所在线路变为 。 是每条线路给定的系数。
你从站点 出发,最初可以免费选择任何经过站点 的线路。对于每个 ,求到达站点 的最短时间。
保证从站点 能够到达所有站点。
输入格式
每个输入文件只有一组测试数据。
第一行两个整数 ,满足 ,,分别表示站点数和线路数。
第二行 个整数 ;第三行 个整数 。它们均满足 。
接下来 行。第 行首先给出整数 (),然后按以下顺序给出 个整数:
$$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
输入:
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