CF938D.Buy a Ticket

Musicians of a popular band "Flayer" have announced that they are going to "make their exit" with a world tour. Of course, they will visit Berland as well.

There are n cities in Berland. People can travel between cities using two-directional train routes; there are exactly m routes, i-th route can be used to go from city v__i to city u__i (and from u__i to v__i), and it costs w__i coins to use this route.

Each city will be visited by "Flayer", and the cost of the concert ticket in i-th city is a__i coins.

You have friends in every city of Berland, and they, knowing about your programming skills, asked you to calculate the minimum possible number of coins they have to pay to visit the concert. For every city i you have to compute the minimum number of coins a person from city i has to spend to travel to some city j (or possibly stay in city i), attend a concert there, and return to city i (if j ≠ i).

Formally, for every you have to calculate , where d(i, j) is the minimum number of coins you have to spend to travel from city i to city j. If there is no way to reach city j from city i, then we consider d(i, j) to be infinitely large.

热门乐队“Flayer”的乐手们宣布，他们将开启一场世界巡演，以此“正式谢幕”。当然，他们也会来到贝尔兰。

贝尔兰共有 $n$ 座城市。人们可通过双向火车线路在城市间通行；总共有 $m$ 条线路，其中第 $i$ 条线路连接城市 $v_i$ 与城市 $u_i$（即可从 $v_i$ 到 $u_i$，也可从 $u_i$ 到 $v_i$），使用该线路需花费 $w_i$ 枚金币。

“Flayer” 将造访贝尔兰的每一座城市，且第 $i$ 座城市的演唱会门票价格为 $a_i$ 枚金币。

你在贝尔兰的每一座城市都有朋友。他们知晓你精通编程，因此请你帮忙计算：每位朋友所需的最少金币数，以便观看一场演唱会。具体而言，对每一座城市 $i$，你需要计算：一位居住在城市 $i$ 的人，前往某座城市 $j$（也可以就是城市 $i$ 本身）观看演唱会，并在结束后返回城市 $i$（若 $j \ne i$）所需支付的最少金币总数。

形式化地，对每个 ，你需要计算 ，其中 $d(i, j)$ 表示从城市 $i$ 到城市 $j$ 所需花费的最少金币数。若无法从城市 $i$ 到达城市 $j$，则定义 $d(i, j)$ 为无穷大。

The first line contains two integers n and m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·105).

Then m lines follow, i-th contains three integers v__i, u__i and w__i (1 ≤ v__i, u__i ≤ n, v__i ≠ u__i, 1 ≤ w__i ≤ 1012) denoting i-th train route. There are no multiple train routes connecting the same pair of cities, that is, for each (v, u) neither extra (v, u) nor (u, v) present in input.

The next line contains n integers _a_1, _a_2, ... a__k (1 ≤ a__i ≤ 1012) — price to attend the concert in i-th city.

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

接下来 $m$ 行，第 $i$ 行包含三个整数 $v_i$、$u_i$ 和 $w_i$（$1 \leq v_i, u_i \leq n$，$v_i \neq u_i$，$1 \leq w_i \leq 10^{12}$），表示第 $i$ 条火车线路。不存在连接同一对城市的多条火车线路，即：对于任意一对城市 $(v, u)$，输入中既不会出现额外的 $(v, u)$，也不会出现 $(u, v)$。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^{12}$）——表示在第 $i$ 个城市举办音乐会的票价。

Print n integers. i-th of them must be equal to the minimum number of coins a person from city i has to spend to travel to some city j (or possibly stay in city i), attend a concert there, and return to city i (if j ≠ i).

输出 $ n $ 个整数。其中第 $ i $ 个整数必须等于：城市 $ i $ 的一个人前往某个城市 $ j $（或可能就留在城市 $ i $），在当地观看一场音乐会，然后再返回城市 $ i $（若 $ j \neq i $）所需花费的最少硬币数量。