题目描述

有 $n$ 座城市，城市编号为 $1 \sim n$。

第 $i$ 座城市会举办一场演唱会。如果一名居民选择去第 $i$ 座城市看演唱会，那么他需要支付门票费用 $a_i$。

城市之间有 $m$ 条双向道路。每条道路连接两座城市，单程通行费用为 $w$。

现在，住在第 $x$ 座城市的居民会选择 恰好一座 城市去看演唱会，并且看完后还要返回自己的城市。

也就是说，如果他选择去第 $i$ 座城市看演唱会，那么总花费为：

$$a_i + 2 \cdot \mathrm{dist}(x,i)$$

其中，$\mathrm{dist}(x,i)$ 表示城市 $x$ 到城市 $i$ 的最短路长度（按单程通行费用计算）。

对于每个城市 $x$，你都需要求出该城市居民的最小总花费。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示城市 $u$ 与城市 $v$ 之间有一条双向道路，单程通行费用为 $w$。

最后一行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示各城市演唱会的门票费用。

数据范围：

• $1 \le n \le 2 \times 10^5$
• $0 \le m \le 2 \times 10^5$
• $1 \le u,v \le n$
• $u \ne v$
• $1 \le w \le 10^{12}$
• $1 \le a_i \le 10^{12}$

保证任意两座城市之间至多有一条道路，且整张图连通。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 座城市居民的最小总花费。

4 4
1 2 3
2 3 2
3 4 4
1 4 10
8 1 7 20

7 1 5 13

Hint

样例解释： 我们分别考虑每座城市的居民：

• 对于城市 $1$，若去城市 $2$ 看演唱会，则总花费为

  $$a_2 + 2 \cdot \mathrm{dist}(1,2) = 1 + 2 \cdot 3 = 7$$

  这是最优方案，因此答案为 $7$。

• 对于城市 $2$，直接在本地看演唱会即可，总花费为

  $$a_2 = 1$$

• 对于城市 $3$，去城市 $2$ 看演唱会更优，总花费为

  $$1 + 2 \cdot 2 = 5$$

• 对于城市 $4$，若去城市 $2$ 看演唱会，最短路长度为

  $$\mathrm{dist}(4,2) = 4 + 2 = 6$$

  因此总花费为

  $$1 + 2 \cdot 6 = 13$$

  比去其他城市都更优，所以答案为 $13$。

因此最终输出为 7 1 5 13。