#include<bits/stdc++.h>
using namespace std;
constexpr int M=55;queue<int>q;
vector<pair<int,int>>e[M],g[M];
int n,m,x,y,z,w[M],ans[M],dep[M],cnt[M];
int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x*f;
}
void dfs(int x,int sum){
	if (sum<ans[x]) ans[x]=sum;
	for (auto [u,v]:e[x]){
		cnt[v]++;
		dfs(u,sum+w[v]*cnt[v]);
		cnt[v]--;
	}
}
int main(){
	n=read();m=read();
	for (int i=1;i<=m;i++) w[i]=read();
	for (int i=1;i<=m;i++){
		x=read();y=read();z=read();
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	memset(dep,-1,sizeof(dep));
	dep[1]=0;q.push(1);
	while (!q.empty()){
		int x=q.front();q.pop();
		for (auto [u,v]:g[x])
			if (!~dep[u])
				dep[u]=dep[x]+1,q.push(u);
	}
	for (int i=1;i<=n;i++)
		for (auto [j,k]:g[i])
			if (dep[i]+1==dep[j])
				e[i].push_back({j,k});
	memset(ans,0x3f,sizeof(ans));
	dfs(1,0);
	for (int i=2;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}