#include<bits/stdc++.h>
using namespace std;
int n,m,v,u,lu[1501][1501],city[1501],cm[1501],b;
bool flag[1501];
void sou(int j,int start){
	flag[j]=1;
	for(int i=1;i<=n;i++){
		if(lu[i][j]!=0&&!flag[i]){
			b+=2*lu[i][j];
			cm[start]=min(cm[start],city[i]+b);
			sou(i,start);
			flag[i]=0;
			b-=2*lu[i][j];
		}
	}
}
int main(){
	//freopen("exciting.in","r",stdin);
	//freopen("exciting.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		cin>>lu[u][v];
		lu[v][u]=lu[u][v];//邻接矩阵 
		//printf("%d\n",lu[v][u]);
	}
	for(int i=1;i<=n;i++){
		cin>>city[i];
		cm[i]=city[i];//第i个城市出发的最小费用设置初始值 
	}
	for(int i=1;i<=n;i++){
		sou(i,i);flag[i]=0;
		cout<<cm[i]<<" ";
	}
	return 0;
}