#include <bits/stdc++.h>
using namespace std;
const int N = 55;
#define int long long
int a[N*N];
struct edge {
int to,w;
edge *nex;
}*head[N];
void add(int u,int v,int w) {
edge *cur=new edge;
cur->to=v;
cur->w=w;
cur->nex=head[u];
head[u]=cur;
}
int vis[N],dis[N];
void spfa(int u) {
queue<int> q;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[u]=0;
q.push(u);
vis[u]=1;
while(!q.empty()) {
u=q.front(); q.pop(); vis[u]=0;
for(edge *cur=head[u];cur;cur=cur->nex) {
if(dis[cur->to]>dis[u]+1) {
dis[cur->to]=dis[u]+1;
if(!vis[cur->to]) {
vis[cur->to]=1;
q.push(cur->to);
}
}
}
}
}
int n,m;
int cnt[N],ans;
int Ans[N];
int cal(int x) {
return cnt[x]*(cnt[x]+1)/2*a[x];
}
void dfs(int u) {
vis[u]=1;
Ans[u]=min(Ans[u],ans);
for(edge *cur=head[u];cur;cur=cur->nex) {
if(vis[cur->to]) continue;
if(dis[cur->to]!=dis[u]+1) continue;
ans-=cal(cur->w);
cnt[cur->w]++;
ans+=cal(cur->w);
dfs(cur->to);
ans-=cal(cur->w);
cnt[cur->w]--;
ans+=cal(cur->w);
}
vis[u]=0;
}
int main() {
memset(Ans,0x3f,sizeof(Ans));
int i,u,v,w,j;
cin>>n>>m;
for(i=1;i<=m;i++) cin>>a[i];
for(i=1;i<=m;i++) {
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
spfa(1);
memset(vis,0,sizeof(vis));
dfs(1);
for(i=2;i<=n;i++) cout<<Ans[i]<<endl;
return 0;
}