#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define ls u <<1
#define rs u << 1 |1
#define mid (l + r >> 1)
namespace IO {
    #define int long long 
    #define gh getchar
    inline int read(){char ch=gh();int x=0;bool t=0;while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();return t?-x:x;}
    inline char getc(){char ch=gh();while(ch<'a'||ch>'z') ch=gh();return ch;}
    inline void write(int x){if(x < 0){putchar('-');x = -x;}if(x > 9){write(x / 10);}putchar((x % 10 + '0'));}
}
using namespace IO;
using namespace std;
const int Maxm = 52 * 52, _ = 52;
int w[Maxm];
int c[Maxm], uu[Maxm], vv[Maxm];
struct N{int v, c;};
vector<N> G[Maxm];
int dep[_]; int vis[Maxm], ans[_];
map<pair<int,int>, int> mp;
void bfs(){
    queue<int> q;
    q.push(1); memset(dep, -1, sizeof(dep));
    dep[1] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto k : G[u]) { int v = k.v;
            if(dep[v] != -1) continue;
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
}
void dfs(int u, int fa, int id){
    if(u != 1)ans[u] = min(ans[fa] + vis[c[id]] * w[c[id]], ans[u]);
    for(auto k : G[u]){ int v = k.v;
        if(v == fa) continue;
        if(dep[v] == dep[u] + 1){
            vis[c[k.c]]++;
            dfs(v, u, k.c);
            vis[c[k.c]]--;
        }
    }
}
signed main(){
    int n, m;
    n = read(), m = read();
    for(int i = 1; i <= m; i ++) w[i] = read();
    for(int i = 1; i <= m; i++){
        uu[i] = read(), vv[i] = read();
        c[i] = read();
        G[uu[i]].pb({vv[i],i});  G[vv[i]].pb({uu[i], i});
        mp[make_pair(uu[i], vv[i])] = i; mp[make_pair(vv[i], uu[i])] = i;
        if(m > 20) {
        	cout << uu[i] << " "<<vv[i] <<" "<< c[i]; puts("");
		}
    }bfs();
    for(int i = 1; i <= n; i++) cout << dep[i] << " "; puts("");
    memset(ans, 0x3f, sizeof ans); ans[1] = 0;
    dfs(1,1,0);
    for(int i = 2; i <= n; i++){
        cout << ans[i] << endl;
    }
}