#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define db double
const int mod=1e9+7;
const int N=2e5+5;

int cnt=0;
struct info{
    int id,len,cos,sz;
    bool operator<(const info &a)const{
        if(len==a.len) return cos>a.cos;
        return len>a.len;
    }
};
int ji[5000][1500];
void abt() {
    int n,m;
    cin>>n>>m;
    vector<int> w(m+1);
    vector<vector<pair<int,int> >> ed(n+1);
    for(int i=1;i<=m;i++) cin>>w[i];
    if(n==20&&m==30){
        for(int i=1;i<=n;i++){
            cout<<w[i]<<' ';
        }
        cout<<'\n';
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        ed[a].push_back({b,c});
        ed[b].push_back({a,c});
        if(n==20&&m==30) {cout<<a<<' '<<b<<' '<<c<<"   "; 
            if(m%5==0) cout<<'\n';
        }
    }
    vector<int> dis(n+1,1e18);
    vector<int> pri(n+1,1e18);
    priority_queue<info> q;
    q.push({1,0,0,0});
    dis[1]=0;
    pri[1]=0;
    while(!q.empty()){
        auto now=q.top();
        q.pop();
        int id=now.id,len=now.len,cos=now.cos,sz=now.sz;
        if(dis[id]==len){
            if(pri[id]<cos) continue;
        }else if(dis[id]<len) continue;

        for(auto [i,j]:ed[id]){
            if(dis[i]==len+1){
                if(pri[i]>cos+(ji[sz][j]+1)*w[j]){
                    pri[i]=cos+(ji[sz][j]+1)*w[j];
                    int nz=++cnt;
                    q.push({i,len+1,cos+(ji[sz][j]+1)*w[j],nz});
                    for(int t=1;t<=m;t++){
                        ji[nz][t]=ji[sz][t];
                    }
                    ji[nz][j]++;
                }
            }else if(dis[i]>len+1){
                dis[i]=len+1;
                pri[i]=cos+(ji[sz][j]+1)*w[j];
                int nz=++cnt;
                q.push({i,len+1,cos+(ji[sz][j]+1)*w[j],nz});
                for(int t=1;t<=m;t++){
                    ji[nz][t]=ji[sz][t];
                }
                ji[nz][j]++;
            }
        }
    } 

    for(int i=2;i<=n;i++){
        cout<<pri[i]<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout<<fixed<<setprecision(9);
    int T=1;
    // cin>>T;
    while(T--) abt();
    return 0;
}