#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[10000][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];

    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});
    }
    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]=min(pri[i],cos+(ji[sz][j]+1)*w[j]);
                ++cnt;
                cnt%=10000;
                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;
}