配点 : 500 点
問題文
在帕肯王国 N 镇 1, 2, \ldots, N 和不同 2 双向连接两个城镇 M 道路 有 1, 2, \ldots, M 。路 i (1 \leq i \leq M) 是一个城镇 A_i 和镇 B_i 双向连接, 2 没有两条不同的道路连接同一组城镇。从任何一个城镇到任何一个城镇 0 您可以沿着多条道路行驶,但不能仅使用道路从一个城镇行驶到另一个城镇。
嗯,今年PA训练营的季节又到了。公园训练营就在城里 由于活动将在 1 举行,因此来自所有城镇的参与者将 转至 1 。由于携带行李出行比较困难,参与者决定乘坐出租车游览城镇。
在帕肯王国 N 出租车公司 1, 2, \ldots, N 并且每个公司都有以下规则。
- 的士公司 i 镇上的出租车 您只能从 i 出发。
- 的士公司 i 的出租车费用与行驶距离无关。 C_i 。
- 的士公司 i 出租车最多有 R_i 只能使用真实道路。
您可以乘坐多辆出租车,但不得使用出租车以外的任何方式游览城镇。
对于参与者来说,往返每个城镇的交通只能使用出租车。 求前往 1 所需的最低总票价。请注意,根据此限制,所有城镇只能乘坐出租车到达。 我们可以证明我们可以移动到 1 。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
- (A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq M)
- 从任何城镇到任何城镇 0 可以穿越多条道路 输出
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq R_i \leq 10 (1 \leq i \leq N)
- 所有输入均为整数 如果有办法做到
入力
输入是按以下格式从标准输入给出的。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M C_1 C_2 \ldots C_N R_1 R_2 \ldots R_N
出力
N 行。 i 行目 (1 \leq i \leq N) 有一个城镇 i 卡拉町 仅在 1 中打印乘坐出租车所需的最低总车费。
入力例 1
5 5 1 2 2 3 3 4 4 5 2 5 100 300 500 200 100 1 2 1 3 1
出力例 1
0 300 700 200 300
帕肯王国如下。

例如,城镇 您可以按如下方式移至 5 卡拉町 仅在 1 。 出租车公司
- 町 5 乘坐 5 出租车到镇上 移至 4 。
- 町 4 乘坐 4 出租车到镇上 移至 1 。
此时需要的总车费为 100+200=300 。总票价为 没有小于 300 的移动方法,因此 300 。 无论您如何从