#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Ts template<typename Ty,typename... Ar>
#define Tp template<typename Ty>
#define ll long long
#define RS register
#define gc getchar
#define pc putchar
#define I inline
using namespace std;
Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}
Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}
namespace WrongIO
{
	Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();if(c=='-')opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-'0',c=gc();x*=opt;return;}
	Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc('0');else pc('-'),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+'0');return;}
    I void writec(char c[]){int len=strlen(c);for(int i=0;i<len;i++)pc(c[i]);}
    I void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
    I void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) c=gc();}
    I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readls(string &s){char c=gc();while(c!='\n') s.push_back(c),c=gc();}
    Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}
} using namespace WrongIO;
int n,m;
int w[5005];
struct awa{
	int v,cl;
};
vector<awa> vt[5005],vat[5005];
int vis[5005]; ll ans[5005];
int cz[5005],mp[5005][5005];
queue<int> q;
void dfs(int u,ll at)
{
	ans[u]=min(ans[u],at);
	for(awa tp:vt[u])
	{
		int v=tp.v;
		cz[tp.cl]++;
		dfs(v,at+1ll*w[tp.cl]*cz[tp.cl]);
		cz[tp.cl]--;
	} return;
}
int main()
{
	read(n,m);
	for(int i=1;i<=m;i++) read(w[i]);
	for(int i=1;i<=m;i++)
	{
		int u,v,w; read(u,v,w);
		vat[u].push_back(awa{v,w});
		vat[v].push_back(awa{u,w});
		mp[u][v]=mp[v][u]=w;
	}
	q.push(1); vis[1]=1;
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		for(awa tp:vat[u])
		{
			int v=tp.v;
			if(vis[v]!=0) continue;
			vis[v]=vis[u]+1; q.push(v);
		}
	}
	memset(ans,0x3f,sizeof(ans));
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(vis[i]+1==vis[j]&&mp[i][j]!=0) vt[i].push_back(awa{j,mp[i][j]});
	dfs(1,0);
	for(int i=2;i<=n;i++) write(ans[i]),pc('\n');
}