#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 50 + 5;
struct edge { int v, c; } e[N * N]; 
int n, m, u, v, c, res, ans[N], cnt[N * N], dep[N], w[N * N];  
vector <edge> G[N], H[N]; 
queue <int> Q; 

void add1 (int u, int v, int c) {
  G[u].push_back((edge){v, c}); 
  G[v].push_back((edge){u, c}); 
}
void add2 (int u, int v, int c) {
  H[u].push_back((edge){v, c}); 
}
void BFS (int s) {
  dep[s] = 0, Q.push(s);
  while (!Q.empty()) {
    int u = Q.front(); Q.pop(); 
    for (auto e : G[u]) 
      if(!dep[e.v] && e.v != s) dep[e.v] = dep[u] + 1, Q.push(e.v); 
  }
}
void dfs (int u) {
  ans[u] = min(ans[u], res); 
  for (auto e : H[u]) {
    ++cnt[e.c], res += cnt[e.c] * w[e.c]; 
    dfs(e.v); 
    res -= cnt[e.c] * w[e.c], --cnt[e.c]; 
  }
}

int main () {
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0); 
  cin >> n >> m;
  rep(i, 1, m) cin >> w[i]; 
  rep(i, 1, m) cin >> u >> v >> c, add1(u, v, c); 
  BFS(1); 
  rep(i, 1, n) for (auto e : G[i]) 
    if(dep[i] + 1 == dep[e.v]) add2(i, e.v, e.c); 
  memset(ans, 0x7f, sizeof(ans)); 
  dfs(1); 
  rep(i, 2, n) cout << ans[i] << '\n'; 
  return 0; 
}