AT_abc422_f.[ABC422F] Eat and Ride

有一个包含 $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$ 时所需消耗的燃料的最小值。

输入通过标准输入给出，格式如下：

$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$：

• 访问顶点 $1$，体重增加 $3$，变为 $3$。
• 消耗 $3$ 单位燃料移动到顶点 $3$，体重增加 $4$，变为 $7$。
• 消耗 $7$ 单位燃料移动到顶点 $5$，体重增加 $5$，变为 $12$。

这样他可以消耗 $10$ 单位燃料到达顶点 $5$。不可能将燃料消耗降到 $9$ 或更少，所以请在第 $5$ 行输出 $10$。

样例解释 2

注意答案可能会超过 $2^{32}$。

数据范围

• $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)$
• 给定的图是连通的。
• 所有输入数据均为整数。

由 ChatGPT 5 翻译