众所周知，Steam 在不同地区购买游戏，是有不同的价格的。小 Y 想找到购买某款开放世界冒险游戏最便宜的方案。

这款游戏在第 $i$ 个国家的售价为 $a_i$。总共有 $n$ 个国家，这 $n$ 个国家之间由 $m$ 条双向道路相连。每次经过第 $i$ 条道路需要付出 $w_i$ 的过路费。小 Y 购买游戏的花费是从自己所在的国家到购买游戏国家的往返过路费与购买游戏费用之和。

小 Y 很快就求出了从自己所在的国家该怎么买最便宜。但小 Y 心胸宽广，想计算出从每个国家出发，最小的购买游戏的花费分别是多少。

第一行两个正整数 $n$ 和 $m$。

接下来 $m$ 行，每行三个正整数 $u, v, w$，表示有一条边连接国家 $u$ 和 $v$，且每经过一次需要付出的代价是 $w$。

接下来一行 $n$ 个数，第 $i$ 个数表示游戏在第 $i$ 个国家的售价 $a_i$。

输出一行 $n$ 个数，第 $i$ 个数表示从第 $i$ 个国家出发，购买游戏的最小花费。

输入文件名： game.in 输出文件名 game.out

T4相关文件下载

数据范围和约定

对于 $30\%$ 的数据，$n \leq 10, \; m \leq 20$；

对于 $70\%$ 的数据，$n \leq 1500, \; m \leq 2000$；

对于 $100\%$ 的数据，$n \leq 200000, \; m \leq 200000, \; a_i, w \leq 10^{9}$。