题目描述

莫阿娜试图追赶毛伊，后者已前往礁石外的岛屿度假，以便从他那里取回特菲提之心。

礁石外有 $n$ 个岛屿，可以通过当地土著完善基础设施的双向渡轮在岛屿之间移动。共有恰好 $m$ 条航线，第 $i$ 条航线用于从岛屿 $v_i$ 前往岛屿 $u_i$（以及从 $u_i$ 前往 $v_i$），费用为 $w_i$ 图格里克。

莫阿娜知道毛伊打算参观所有岛屿并开阔视野。莫阿娜还知道每个岛屿的酋长都会收取参观税（完善的基础设施需要图格里克）。参观第 $i$ 个岛屿的税费为 $a_i$ 图格里克。

莫阿娜计划利用风暴抵达礁石外，但她不知道风暴结束后自己会出现在哪个岛屿上。因此，她试图计算无论自己被冲上哪个岛屿，为了追上毛伊所需的最少图格里克数量，以便随身携带足够的图格里克去冒险。

形式化地说，对于每个 $u \in [1, n]$，需要计算 $\min\limits_{v=1}^n 2 \mathtt{dist}(u, v) + a_v$，其中 $\mathtt{dist}(u, v)$ 表示从岛屿 $u$ 到岛屿 $v$ 的旅行所需的最少图格里克数量。

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$；$1 \le m \le 2 \cdot 10^5$）。

下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^{12}$）——表示参观岛屿 $i$ 的税费。

接下来 $m$ 行，第 $i$ 行包含三个整数 $v_i$、$u_i$ 和 $w_i$（$1 \le v_i, u_i \le n$；$v_i \ne u_i$；$1 \le w_i \le 10^9$），定义第 $i$ 条渡轮航线。每对岛屿之间最多存在一条渡轮航线，也就是说，对于任意一对 $(v, u)$，输入数据中不会出现 $(u, v)$ 或额外的 $(v, u)$。

输出格式

输出 $n$ 个整数。第 $i$ 个整数应为莫阿娜从岛屿 $i$ 出发，前往某个岛屿 $j$（或留在岛屿 $i$），支付岛屿参观税并取回特菲提之心，然后返回岛屿 $i$（如果 $j \ne i$）所需花费的最少图格里克数量。

4 2
15 3 10 2
2 3 2
3 4 3

15 3 7 2

3 3
10 20 30
1 2 1
1 3 1
2 3 1

10 12 12