#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=55;
ll n,m,W[N],d[N],cnt[N],ans[N];
vector<pii>to[N],es[N];
void dfs(ll x,ll s){
	ans[x]=min(ans[x],s);
	for(pii e:es[x]){
		ll y=e.first,w=e.second;
		cnt[w]++;
		dfs(y,s+cnt[w]*W[w]);
		cnt[w]--;
	}
}
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	n=read(),m=read();
	rep(i,1,m)W[i]=read();
	rep(i,1,n)ans[i]=1e18;
	rep(i,1,m){
		ll x=read(),y=read(),z=read();
		to[x].push_back(make_pair(y,z));
		to[y].push_back(make_pair(x,z));
	}
	queue<ll>q;
	q.push(1),d[1]=1;
	while(!q.empty()){
		ll u=q.front();q.pop();
		for(pii e:to[u]){
			ll v=e.first,w=e.second;
			if(!d[v]){
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	rep(u,1,n){
		for(pii e:to[u]){
			ll v=e.first,w=e.second;
			if(d[v]==d[u]+1)es[u].push_back(make_pair(v,w));
		}
	}
	dfs(1,0);
	rep(i,2,n)write(ans[i]),putchar('\n');
	return 0;
}