题目描述

强哥所在的社区有 $N$ 户人家，编号为 $1, 2, \dots, N$，社区中有 $M$ 条双向小路连接这些人家。 每户人家 $i$ 都有一个“温暖值” $A_i$，表示该户人家需要帮助的程度（数值越大表示越需要帮助）。 第 $j$ 条小路连接人家 $U_j$ 和 $V_j$，这条小路的“通行难度”为 $B_j$。

强哥打算从自己家（1 号）出发，为其他人家送去温暖。 一条送温暖路径的“总付出”定义为：路径上经过的所有人家的温暖值之和，加上所有经过的小路的通行难度之和。

对于每户人家 $i$（$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$

输出格式

输出一行，包含 $N-1$ 个整数，用空格分隔，依次表示 $i=2,3,\dots,N$ 的答案。

输入输出样例

样例 1

输入

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

输出

4 9

说明

• 到 2 号人家的最小总付出路径：1 → 2，付出 = $A_1 + A_2 + B_{1,2} = 1 + 2 + 1 = 4$
• 到 3 号人家的最小总付出路径：1 → 2 → 3，付出 = $A_1 + A_2 + A_3 + B_{1,2} + B_{2,3} = 1 + 2 + 3 + 1 + 2 = 9$

样例 2

输入

2 1
0 1
1 2 3

输出

4

说明 到 2 号人家的路径：1 → 2，付出 = $A_1 + A_2 + B_{1,2} = 0 + 1 + 3 = 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

输出

2832044198 2824130042 4696218483 2805069468

数据范围

• $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$
• 所有输入均为整数

注意： 答案可能很大，请使用 64 位整数计算。