最短路 3

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单连通无向图。每个顶点 $i\,(1 \le i \le N)$ 有权值 $A_i$。每条边 $j\,(1 \le j \le 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$ 对应的答案。

样例

3 3
1 2 3
1 2 1
1 3 6
2 3 2

4 9

考虑从顶点 $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$。

2 1
0 1
1 2 3

4

5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

2832044198 2824130042 4696218483 2805069468

数据范围

• $2 \le N \le 2 \times 10^5$
• $N-1 \le M \le 2 \times 10^5$
• $1 \le U_j \lt V_j \le N$
• 当 $i \neq j$ 时,$(U_i, V_i) \neq (U_j, V_j)$。
• 图是连通的。
• $0 \le A_i \le 10^9$
• $0 \le B_j \le 10^9$
• 所有输入值均为整数。

提示

注意:答案可能超出 32 位整数能表示的范围。