//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define all(x) (x).begin(),(x).end()
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
int const N=3e3+10;
int n,m,w[N],dep[N],ans[N],cnt[N];
vector< pair<int,int> >a[N];
inline void dfs(int x,int sm){
    ans[x]=min(ans[x],sm);
    for (auto i:a[x]){
        int v=i.first,c=i.second;
        if (dep[v]!=dep[x]+1) continue;
        ++cnt[c],dfs(v,sm+w[c]*cnt[c]),--cnt[c];
    }
}
inline void solve(){
    cin>>n>>m;
    rep(i,1,m) cin>>w[i];
    rep(i,1,m){
        int u,v,c;cin>>u>>v>>c;
        a[u].push_back({v,c});
        a[v].push_back({u,c});
    }
    queue<int>q;q.push(1),dep[1]=1;
    while (!q.empty()){
        int x=q.front();q.pop();
        for (auto i:a[x]){
            int v=i.first;
            if (dep[v]) continue;
            dep[v]=dep[x]+1,q.push(v);
        }
    }
    memset(ans,0x3f,sizeof(ans)),dfs(1,0);
    rep(i,2,n) cout<<ans[i]<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while (t--) solve();
    cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}