bool M1;
#include<bits/stdc++.h>
using namespace std;
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time cerr<<(clock()-ST)*1.0/CLOCKS_PER_SEC<<'\n'
//#define int long long
#define ll long long
#define db double
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
#define fr first
#define sc second
template<typename T> void ckmin(T &x,T y){x=min(x,y);}
template<typename T> void ckmax(T &x,T y){x=max(x,y);}
mt19937 rnd(time(0));
const int N=55;
const int M=2505;
const int inf=1e9;
const int mod=1000000007;
int n,m,x[M];
int cnte,to[M],col[M],nxt[M],head[N];
inline void add(int u,int v,int w){
	to[++cnte]=v;
	col[cnte]=w;
	nxt[cnte]=head[u];
	head[u]=cnte;
}
int dis[N],T[M],ans;
bool vis[N];
queue<int> q;
void dfs(int u,int t,int val,int stp){
    if(val>=ans) return;
    if(stp>dis[u]) return;
    if(u==t){
        if(dis[t]==stp) ans=min(ans,val);
        return;
    }
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(vis[v]) continue;
        T[col[i]]++;
        vis[u]=1;
        if(dis[v]==stp+1) dfs(v,t,val+T[col[i]]*x[col[i]],stp+1);
        vis[u]=0;
        T[col[i]]--;
    }
    return;
}
void bfs(int s,int t){
    for(int i=0;i<N;i++) dis[i]=inf;
    q.push(s);
    dis[s]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return;
}
bool M2;
signed main(){
//	look_memory;
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>x[i];
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		add(u,v,w),add(v,u,w);
	}
	for(int v=2;v<=n;v++){
		bfs(1,v);
		ans=inf;
		for(int i=1;i<=n;i++) vis[i]=0;
		dfs(1,v,0,0);
		cout<<ans<<"\n";		
	}
	return 0;
}