题目描述
发动机内部有n个能量节点，能量节点之间有m条线路，每条线路连接着两个能量节点。能量经过每条线路的时候都有一定的能量损耗，激发第i个节点的能量损耗是a[i]。发动机每次运行的时候，能量会从一个节点流出，沿着线路流动，激发某个节点之后回流到起点。激发的节点可以是起点本身。
程序需要计算出以每个节点作为起点，能量从流出到回流整个过程的最少能量消耗。
输入
第一行两个整数，n和m。(n,m <= 100000)
接下来m行，每行三个数u,v,w，表示存在连接u和v的一条线路，能量经过这条线路的损耗是w（w <= 100000）。
接下来n个整数，分别表示a[1]到a[n](a[i] <= 100000)。
输出
n个空格隔开的整数。按照编号从1到n的顺序，依次输出能量从每个节点流出，激发一个节点，最后回流自身的最少能量消耗。
样例输入
4 2
1 2 4
2 3 7
6 20 1 25样例输出
6 14 1 25