#include<iostream>
#include<cstdio>
#include<queue>
#define maxn 55
#define maxm 1505
#define inf 2100000000
using namespace std;
int n,m,w[maxm],u,v,c,dep[maxn],ans[maxn],b[maxn]; struct node{int to,nex,col;}a[maxm]; 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&&ans[a[i].to]>ans[p]+w[a[i].col]*(b[a[i].col]+1)){
		ans[a[i].to]=ans[p]+w[a[i].col]*(++b[a[i].col]); dfs(a[i].to); b[a[i].col]--;
	}
}
int main(){
	scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&w[i]);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&u,&v,&c),add(u,v,c);
	bfs(); for(int i=2;i<=n;i++) ans[i]=inf; dfs(1); for(int i=2;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}