U287351 H.NANA去上课

作为acmer，NANA也是需要去参加集训的。现在有$n$个城市，每个城市都在举办集训，在城市$i$参加集训需要报名费$a_i$块钱。你也可以选择可以沿着双向的道路在城市之间移动，有$m$条道路，第$i$条道路可以用于从城市$u_i$到$vi$以及从城市$v_i$到$u_i$，使用这条道路需要花费$w_i$块钱。 NANA在每个城市都有好朋友，他们听说你的编程能力超群，想让你帮忙算一算他们去参加集训的最小花费。对于每个城市$i$，你需要计算一个来自城市$i$的人前往城市$j$（$j$可能等于$i$），在那里参加集训，然后返回城市$i$（如果$i$等于$j$就不需要花路费了）的最小花费。

第一行两个整数$n$和$m$表示城市数和道路数。 接下来$m$行，每行三个正整数$x_i,y_i,w_i$描述第$i$条边。数据保证没有重边和自环。 最后一行$n$个整数，第$i$个整数$a_i$表示在第$i$个城市参加集训的报名费。

输出一行$n$个整数，第$i$个整数表示从第$i$个城市出发到其他城市参加集训的路费、集训费、回到城市i的路费加起来的最小值。

**样例解释** 对于城市1，在自己的城市参加集训花费最小。 对于城市2，可以花8块路费前往城市1，再花6块报名费。 对于城市3，在自己的城市参加集训花费最小。 对于城市4，因为他到达不了其他城市，所以只好在自己的城市参加集训。 **数据规模与约定** 保证$2\le n\le 2*10^5,1\le m \leq 2*10^5,1\leq v_i,u_i\leq n,u_i \neq v_i,1\leq w_i\leq 10^{12},1\leq a_i\leq 10^{12}$。 保证不存在重边。