103623: [Atcoder]ABC362 D - Shortest Path 3

Problem Statement

You are given a simple connected undirected graph with $N$ vertices and $M$ edges. Each vertex $i\,(1\leq i \leq N)$ has a weight $A_i$. Each edge $j\,(1\leq j \leq M)$ connects vertices $U_j$ and $V_j$ bidirectionally and has a weight $B_j$.

The weight of a path in this graph is defined as the sum of the weights of the vertices and edges that appear on the path.

For each $i=2,3,\dots,N$, solve the following problem:

• Find the minimum weight of a path from vertex $1$ to vertex $i$.

Constraints

• $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$
• $(U_i, V_i) \neq (U_j, V_j)$ if $i \neq j$.
• The graph is connected.
• $0 \leq A_i \leq 10^9$
• $0 \leq B_j \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answers for $i=2,3,\dots,N$ in a single line, separated by spaces.

Sample Input 1

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

Sample Output 1

4 9

Consider the paths from vertex $1$ to vertex $2$. The weight of the path $1 \to 2$ is $A_1 + B_1 + A_2 = 1 + 1 + 2 = 4$, and the weight of the path $1 \to 3 \to 2$ is $A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14$. The minimum weight is $4$.

Consider the paths from vertex $1$ to vertex $3$. The weight of the path $1 \to 3$ is $A_1 + B_2 + A_3 = 1 + 6 + 3 = 10$, and the weight of the path $1 \to 2 \to 3$ is $A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9$. The minimum weight is $9$.

Sample Input 2

2 1
0 1
1 2 3

Sample Output 2

4

Sample Input 3

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

Sample Output 3

2832044198 2824130042 4696218483 2805069468

Note that the answers may not fit in a 32-bit integer.

问题陈述

给定一个简单连通无向图，包含N个顶点和M条边。每个顶点i（1≤i≤N）有一个权重A_i。每条边j（1≤j≤M）双向连接顶点U_j和V_j，并有一个权重B_j。

图中路径的权重定义为路径上出现的顶点和边的权重之和。

对于每个i=2,3,…,N，解决以下问题：

• 找到从顶点1到顶点i的路径的最小权重。

约束条件

• 2 ≤ N ≤ 2 × 10^5
• N-1 ≤ M ≤ 2 × 10^5
• 1 ≤ U_j < V_j ≤ N
• 如果i ≠ j，则(U_i, V_i) ≠ (U_j, V_j)。
• 图是连通的。
• 0 ≤ A_i ≤ 10^9
• 0 ≤ B_j ≤ 10^9
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

N M
A_1 A_2 … A_N
U_1 V_1 B_1
U_2 V_2 B_2
⋮
U_M V_M B_M

输出

在一行中打印i=2,3,…,N的答案，用空格分隔。

示例输入1

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

示例输出1

4 9

考虑从顶点1到顶点2的路径。 路径1 → 2的权重是A_1 + B_1 + A_2 = 1 + 1 + 2 = 4，路径1 → 3 → 2的权重是A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14。最小权重是4。

考虑从顶点1到顶点3的路径。 路径1 → 3的权重是A_1 + B_2 + A_3 = 1 + 6 + 3 = 10，路径1 → 2 → 3的权重是A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9。最小权重是9。

示例输入2

2 1
0 1
1 2 3

示例输出2

4

示例输入3

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

示例输出3

2832044198 2824130042 4696218483 2805069468

注意，答案可能不适合32位整数