#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 998244353;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> w(m + 1), ans(n + 1), len(n + 1, n + 1), cnt(m + 1);
    for (int i = 1; i <= m; i++) cin >> w[i];
    vector<vector<pair<int, int>>> G(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        G[u].push_back({v, c});
        G[v].push_back({u, c});
    }
    auto dfs = [&](auto dfs, int u, int dep, int val) -> void {
        if (dep < len[u]) {
            len[u] = dep;
            ans[u] = val;
        } else if (dep == len[u]) {
            ans[u] = min(ans[u], val);
        }
        dep++;
        for (auto [v, c] : G[u]) {
            if (len[v] < dep) continue;
            cnt[c]++;
            val += cnt[c] * w[c];
            dfs(dfs, v, dep, val);
            val -= cnt[c] * w[c];
            cnt[c]--;
        }
    };
    len[0] = 0;
    dfs(dfs, 1, 0, 0);
    for (int i = 2; i <= n; i++) cout << ans[i] << '\n';
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) solve();
    return 0;
}