无聊的小 biu 来到了电影之城，他发现这里有 n 个电影院，而且每个电影院的电影票价是不同的，有一些电影院之间有双向连通的道路，想要通过某条道路也有不同的花费，小 biu 想知道，他以每一个电影院为起点(当然也可以原地不动)，最少需要多少花费可以看到电影并返回到起点。

注：如果当前影院太贵，小 biu 会考虑花一定的路费去别的地方看电影，并返回。

第 1 行：两个整数 n,m， n 表示城市中电影院的个数， m 表示电影院之间的道路总数。 (1\leq n \leq 10^5,1\leq m \leq 3\times10^5)

第 n 行： n 个正整数，第 i 个正整数表示在第 i 个电影院看电影的票价 vla[i] 。  (1\leq val[i] \leq10^3)

第 3~m+2 行：每行三个正整数， u,v,w 表示电影院 u 与电影院 v 之间有一条花费为 w 的道路。 (1\leq u,v \leq10^3,1\leq w \leq 1000)

输出 n 行每行一个正整数。

第 i 行输出的正整数表示从第 i 个电影院出发，最少需要多少花费可以看到电影。

样例解释:

对于在 1 号电影院，直接在本地观看，花费为 1；

对于在 2 号电影院，直接在本地观看，花费为 2 ；

对于在 3 号电影院，直接在本地观看，花费为 3 ；

对于在 4 号电影院，通过道路 1—>4 去 4 号电影院观看，花费为 1*2+1=3  ；