#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 55 , M = 1300;
int n , m , d[N] , cnt[M] , w[M] , ans[N];
vector<pair<int , int> >g[N]; bool vis[N];
void Dfs(int u , int dis)
{
	ans[u] = min(ans[u] , dis) , vis[u] = 1;
	for(auto [v , c] : g[u])
		if(!vis[v] && d[u] + 1 == d[v])
			Dfs(v , dis + w[c] * ++cnt[c]) , cnt[c]--;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i++)
		cin >> w[i];
	for(int i = 1 ; i <= m ; i++)
	{
		int u , v , c; cin >> u >> v >> c;
		g[u].push_back({v , c});
		g[v].push_back({u , c});
	}
	memset(d , 0x3f , sizeof d);
	queue<int>q; q.push(1) , d[1] = 0;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(auto [v , c] : g[u])
			if(d[u] + 1 < d[v])
			{
				d[v] = d[u] + 1;
				q.push(v);
			}
	}
	memset(ans , 0x3f , sizeof ans);
	Dfs(1 , 0);
	for(int i = 2 ; i <= n ; i++)
		cout << ans[i] << "\n";
	return 0;
}