AT_abc362_d [ABC362D] Shortest Path 3

给定一个有 $N$ 个顶点、$M$ 条边的简单连通无向图。顶点 $i$（$1\leq i \leq N$）有权值 $A_i$。第 $j$ 条边（$1\leq j \leq M$）连接顶点 $U_j$ 和 $V_j$（双向），权值为 $B_j$。 在这张图上，一条路径的权值定义为路径上所有出现的顶点权值与边权值的总和。 对于每个 $i=2,3,\dots,N$，请解决以下问题： - 求从顶点 $1$ 到顶点 $i$ 的所有路径中，权值最小的那条路径的权值。

输入以如下格式从标准输入给出。 > $N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$ $U_1$ $V_1$ $B_1$ $U_2$ $V_2$ $B_2$ $\vdots$ $U_M$ $V_M$ $B_M$

请按顺序输出 $i=2,3,\dots,N$ 的答案，用空格分隔，输出一行。

## 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $N-1 \leq M \leq 2 \times 10^5$ - $1 \leq U_j < V_j \leq N$ - 若 $i \neq j$，则 $(U_i,V_i) \neq (U_j,V_j)$ - 图是连通的 - $0 \leq A_i \leq 10^9$ - $0 \leq B_j \leq 10^9$ - 所有输入均为整数 ## 样例解释 1 考虑从顶点 $1$ 到顶点 $2$ 的路径。路径 $1 \to 2$ 的权值为 $A_1+B_1+A_2=1+1+2=4$，路径 $1 \to 3 \to 2$ 的权值为 $A_1+B_2+A_3+B_3+A_2=1+6+3+2+2=14$，最小权值为 $4$。 考虑从顶点 $1$ 到顶点 $3$ 的路径。路径 $1 \to 3$ 的权值为 $A_1+B_2+A_3=1+6+3=10$，路径 $1 \to 2 \to 3$ 的权值为 $A_1+B_1+A_2+B_3+A_3=1+1+2+2+3=9$，最小权值为 $9$。 ## 样例解释 3 请注意，答案可能超出 32 位整数范围。 由 ChatGPT 4.1 翻译