#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005];
int nxt[2505],head[55],go[2505],cost[2505],ans[55],k;
int mp[55][55],dis[55];
int cnt[55];
void add(int u,int v,int w)
{
	nxt[++k]=head[u];
	head[u]=k;
	go[k]=v;
	cost[k]=w;
}
void dfs(int x,int sum)
{
	ans[x]=min(ans[x],sum);
	for(int i=head[x];i;i=nxt[i])
	{
		int g=go[i],w=cost[i];
		cnt[w]++;
		dfs(g,sum+cnt[w]*a[w]);
		cnt[w]--;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		mp[u][v]=mp[v][u]=w;
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(mp[j][k]) dis[k]=min(dis[k],dis[j]+1); 
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(mp[i][j]&&dis[j]==dis[i]+1) add(i,j,mp[i][j]);
		}
	}
	memset(ans,0x3f,sizeof(ans));
	dfs(1,0);
	for(int i=2;i<=n;i++)
	{
		cout<<ans[i]<<"\n";
	}
}