#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=510;
const ll INF=1e13;

int n,m;
ll dis[N][N],a[N];
ll g[N][N],w[N][2],ans,minn;
int mch[N];bool vis[N][2];

void input(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		for (int j=1;j<=n;j++){
			dis[i][j]=INF;g[i][j]=-INF;
		}
	}
	for (int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		dis[u][v]=w;
	}
}

void floyd(){
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				dis[i][j]=min(1LL*dis[i][j],1LL*dis[i][k]+dis[k][j]);
}

void build(){
	for (int i=1;i<=n;i++){
		g[i][i]=-a[i];w[i][0]=-a[i];
		for (int j=1;j<=n;j++)
			if (dis[i][j]!=INF&&i!=j){
				g[i][j]=-dis[i][j];
				w[i][0]=max(w[i][0],g[i][j]);
			}
	}
}

bool dfs(int u){
	vis[u][0]=1;
	for (int v=1;v<=n;v++){
		if (g[u][v]==-INF||vis[v][1]) continue;
		ll t=1LL*w[u][0]+w[v][1]-g[u][v];
		if (!t){
			vis[v][1]=1;
			if (!mch[v]||dfs(mch[v])){
				mch[v]=u;return 1;
			}
		}else minn=min(minn,t);
	}
	return 0;
}

void KM(){
	for (int i=1;i<=n;i++){
		minn=INF;memset(vis,0,sizeof(vis));
		while (1){
			if (dfs(i)) break;
			for (int j=1;j<=n;j++){
				if (vis[j][0]) w[j][0]-=1LL*minn;
				if (vis[j][1]) w[j][1]+=1LL*minn;
				vis[j][0]=vis[j][1]=0;
			}
			minn=INF;
		}
	}
	for (int i=1;i<=n;i++) ans+=g[mch[i]][i];
	printf("%lld\n",-ans);
}

int main(){
	input();
	floyd();
	build();
	KM();
	return 0;
}

快调吐了，救救孩子。