#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 55
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,w[maxn*maxn];
vector<pair<int,int> >O[maxn*maxn];
int f[maxn*maxn][maxn][maxn],g[maxn][maxn],vis[maxn][maxn];
const int inf=1e9;
signed main(void){
	int i,j,k,l,o,x,y,z;
	read(n);read(m);
	for (i=1;i<=m;i++) read(w[i]);
	for (i=1;i<=m;i++) {
		read(x),read(y);read(z);
		O[z].push_back(mk(x,y));
	}
	memset(f,0x3f,sizeof(f));
	for (i=1;i<=n;i++) f[0][i][i]=0;
	for (k=1;k<=m;k++) {
		int nums=O[k].size();
		if (!nums) continue;
		for (auto tmp:O[k]) vis[tmp.fi][tmp.se]=1;
		for (l=1;l<=nums;l++) {
			for (o=1;o<=n;o++) {
				for (j=1;j<=n;j++) if (vis[o][j]) {
					for (i=1;i<=n;i++)
						f[l][i][j]=min(f[l][i][j],f[l-1][i][o]+l*w[k]);
				}
			}
		}
		for (auto tmp:O[k]) vis[tmp.fi][tmp.se]=0;
		
		for (i=1;i<=n;i++) {
			for (j=1;j<=n;j++) {
				int sum=inf;
				for (l=0;l<=nums;l++) sum=min(sum,f[l][i][j]),f[l][i][j]=inf;
				f[0][i][j]=sum;
			} 
		} 
	}
	for (i=2;i<=n;i++) printf("%d\n",f[0][1][i]);
	return 0;
}