分数: 500 点
问题陈述
有一个连通无向图 N 顶点和 M 边缘。 顶点编号为顶点 1, 顶点 2,\ldots, 顶点 N,以及 i第边缘 (1\le i\le M) 连接顶点 u _ i 和 v _ i.
对于 i=1,2,\ldots,N,解决以下问题:
最初,高桥的体重是 0.
他开车去拜访顶点 1 并向顶点移动 i。 当他访问顶点时 v\ (1\le v\le N),他的体重增加了 W _ v.
他乘坐的汽车可以沿着边缘移动。 当他穿过边缘时,让 X 是他当时的体重,车耗 X 燃料。
求他到达顶点所消耗的最少燃料量 i.
约束
- 1\le N\le5000
- 1\le M\le5000
- 1\le W _ i\le10 ^ 9\ (1\le i\le N)
- 1\le u _ i\le v _ i\le N\ (1\le i\le M)
- 给定的图形已连接。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M W _ 1 W _ 2 \ldots W _ N u _ 1 v _ 1 u _ 2 v _ 2 \vdots u _ M v _ M
输出
输出超过 N 行。 上 i第行 (1\le i\le N),输出高桥到达顶点所需的燃料量 i.
示例输入 1
5 6 3 1 4 1 5 1 2 1 3 2 3 2 4 3 5 4 5
示例输出 1
0 3 3 7 10
给出的图表如下:

例如,高桥可以到达顶点 5 通过访问顶点 1 然后执行如下操作:
- 他访问顶点 1。他的体重增加了 3,成为 3.
- 他消耗 3 移动到顶点的燃料 3。他的体重增加了 4,成为 7.
- 他消耗 7 移动到顶点的燃料 5。他的体重增加了 5,成为 12.

通过这种方式,他可以到达顶点 5 通过消费 10 燃料。 不可能将油耗降低到 9 或更少,因此输出 10 上 5第行。
示例输入 2
5 4 1000000000 1000000000 1000000000 1000000000 1000000000 1 2 2 3 3 4 4 5
示例输出 2
0 1000000000 3000000000 6000000000 10000000000
请注意,答案可能会超过 2 ^ {32}.
示例输入 3
10 20 74931 58277 33783 91022 53003 11085 65924 63548 78622 77307 1 8 3 6 5 10 4 6 1 3 1 7 2 6 7 10 8 9 3 4 4 4 4 6 6 6 5 10 1 7 4 5 1 2 3 7 2 3 5 8
示例输出 3
0 74931 74931 183645 213410 183645 74931 74931 213410 215786