#include <bits/stdc++.h>
#define int long long
using namespace std;
#define PII pair<int,int>
int n, m;

void solve () {
    cin>>n>>m;
    vector<int>gs(m+1,0);
    vector<int>a(n+1,0);
    vector<vector<pair<int,int>>>g(n+1);
    for(int i=1;i<=m;i++)cin>>a[i];
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }    
    vector<int>dis(n+1,1e18);
    vector<int>cost(n+1,1e18);
    dis[1]=0;
    queue<int>q;
    // priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push(1);
    cost[1]=0;
    while(q.size()){
        auto u=q.front();
        q.pop();
        for(auto [v,w]:g[u]){
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    auto dfs=[&](auto &&self,int u,int dist)->void{
        {}
        for(auto [v,w]:g[u]){
            if(dist+1!=dis[v])continue;
            gs[w]++;
            if(cost[v]>cost[u]+gs[w]*a[w]){
                cost[v]=cost[u]+gs[w]*a[w];
            }
            self(self,v,dist+1);
            gs[w]--;
        }
    };
    dfs(dfs,1,0);
    for(int i=2;i<=n;i++){
        cout<<cost[i]<<"\n";
    }

}
signed main () {
    int T = 1; 
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //cin>>T;
    while (T --) solve ();
    return 0;
}