#include<iostream>
#include<cstdio>
#include<queue>
#define maxn 5005
#define maxm 15005
#define inf 1e9
#define int long long
using namespace std;
int n,m,w[maxm],u,v,c,dep[maxn],ans[maxn],b[maxn],fin[maxn]; struct node{int to,nex,col;}a[maxm*2]; int head[maxn],cnt=0;
void add(int from,int to,int col){a[++cnt].to=to; a[cnt].col=col; a[cnt].nex=head[from]; head[from]=cnt;}
queue<int> q; void bfs(){
	q.push(1); dep[1]=1; while(!q.empty()){
		int top=q.front(); q.pop();
		for(int i=head[top];i;i=a[i].nex) if(!dep[a[i].to]) dep[a[i].to]=dep[top]+1,q.push(a[i].to);
	}
}
void dfs(int p){
	for(int i=head[p];i;i=a[i].nex) if(dep[a[i].to]==dep[p]+1){
		int res=ans[a[i].to]; ans[a[i].to]=min(ans[p]+w[a[i].col]*(++b[a[i].col]),ans[a[i].to]);
		fin[a[i].to]=min(fin[a[i].to],ans[a[i].to]); dfs(a[i].to); b[a[i].col]--; ans[a[i].to]=res;
	}
}
signed main(){
	scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) scanf("%lld",&w[i]);
	for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&u,&v,&c),add(u,v,c),add(v,u,c);
	bfs(); for(int i=2;i<=n;i++) ans[i]=fin[i]=inf; dfs(1); for(int i=2;i<=n;i++) printf("%lld\n",fin[i]);
	return 0;
}