#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define double long double
typedef long long ull;
typedef unsigned long long uull;
typedef pair<int, int> PII;
typedef pair<int,PII> PIII;
// typedef __int128 lll;
// mt19937 rnd1(random_device{}());
// mt19937_64 rnd2(random_device{}());
// uniform_int_depthtribution<int> deptht1(0,2e18);    //定义deptht1为0——100的随机整数
// uniform_real_depthtribution<double> deptht2(-10,10);    //定义deptht2为-10——10的随机浮点数
//#define mp make_pair
//fflush(stdout);
//random_shuffle()
//mod = 1e9+7+rand() 哈希时的随机模数
const int mod = 998244353,INF = 1e9;
ull qpow(ull a, ull b)
{
    ull res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
inline int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
inline int lcm(int a, int b) { return a / gcd(a, b) * b; }
const int N = 110,M = 5010;

int w[M],d[N],vis[10010],dis[N];
int h[N],id[M<<1],ne[M<<1],v[M<<1],idx = 1;

void add(int x,int y,int z)
{
    id[idx] = z,v[idx] = y,ne[idx] = h[x],h[x] = idx++;
}

void bfs(int u)
{
    queue<int> q;
    d[u] = 1;
    q.push(u);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i=h[t];i;i=ne[i])
        {
            int j = v[i];
            if(d[j]) continue;
            d[j] = d[t]+1;
            q.push(j);
        }
    }
}

void dfs(int u)
{
    for(int i=h[u];i;i=ne[i])
    {
        int j = v[i];
        if(d[j]!=d[u]+1) continue;
        vis[w[id[i]]]++;
        dis[j] = min(dis[j],dis[u]+vis[w[id[i]]]*w[id[i]]);
        dfs(j);
        vis[w[id[i]]]--;
    }
}

void solve()
{
    int n,m;
    cin>>n>>m;
    memset(dis,0x3f,sizeof(dis));
    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;
        add(a,b,c);
        add(b,a,c);
    }
    dis[1] = 0;
    bfs(1);
    dfs(1);
    for(int i=2;i<=n;i++) cout<<dis[i]<<'\n';
}

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