#include <stdio.h>
#include <string.h>
#include <vector>

#define inf (int)1e9
#define tmax 55
#define nmax 55
#define mmax 305
#define pb push_back

using namespace std;
typedef pair<char,char> ii;

int tot,i,n,m,n1,n2,vl,p,q,nod,nodt,nnod;
char v[nmax][tmax];
unsigned short int prev[nmax * nmax * tmax];
short int cap[nmax][nmax],fl[nmax][nmax][nmax][nmax];
ii st[nmax * nmax * tmax];
vector <int> e[nmax];

int drum(int x) {
	memset(v,0,sizeof(v));
	v[0][0] = 1;
	memset(st,0,sizeof(st));
	st[p = q = 1] = ii(0,0);
	prev[1] = 0;
	while(q <= p) {
		nod = st[q].first; nodt = st[q].second;
		for(int i = 0; i < (int)e[nod].size(); i++) {
			if(!v[e[nod][i]][nodt + 1] && nodt + 1 <= x && cap[nod][e[nod][i]] > fl[nod][nodt][e[nod][i]][nodt + 1]) {
				v[e[nod][i]][nodt + 1] = 1;
				st[++p] = ii(e[nod][i],nodt + 1);
				prev[p] = q;
			}
			if(!v[e[nod][i]][nodt - 1] && nodt - 1 > 0 && cap[nod][e[nod][i]] > fl[nod][nodt][e[nod][i]][nodt - 1]) {
				v[e[nod][i]][nodt - 1] = 1;
				st[++p] = ii(e[nod][i],nodt - 1);
				prev[p] = q;
			}
			if(st[p].first == 1 && st[p].second == x) break;
		}
		if(st[p].first == 1 && st[p].second == x) break;
		q++;
	}
	if(st[p].first == 1 && st[p].second == x) {
		int z = p,mini = inf;
		while(prev[z]) {
			mini = min(mini,cap[st[prev[z]].first][st[z].first] - fl[st[prev[z]].first][st[prev[x]].second][st[z].first][st[z].second]);
			z = prev[z];
		}
		z = p;
		while(prev[z]) {
			fl[st[prev[z]].first][st[prev[z]].second][st[z].first][st[z].second] += mini;
			fl[st[z].first][st[z].second][st[prev[z]].first][st[prev[z]].second] -= mini;
			z = prev[z];
		}
		return 1;
	}
	else return 0;
}

int flux(int x) {
	memset(fl,0,sizeof(fl));
	while(drum(x)) ;
	int rez = 0;
	for(int i = 0; i < (int)e[1].size(); i++) 
		if(fl[e[1][i]][x - 1][1][x] > 0) rez += (int)fl[e[1][i]][x - 1][1][x];
	return rez;
}

int cauta(int first,int last) {
	int re = 0,mi;
	while(first <= last) {
		mi = (first + last) / 2;
		if(flux(mi) >= tot) {
			re = mi;
			last = mi - 1;
		}
		else first = mi + 1;
	}
	return re;
}

int main() {
	freopen("algola.in","r",stdin);
	freopen("algola.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(i = 1; i <= n; i++) {
		scanf("%hd",&cap[0][i]);
		tot += cap[0][i];
		cap[i][i] = 250;
		e[0].pb(i); e[i].pb(0); e[i].pb(i);
	}
	if(tot == cap[0][1]) {
		printf("0\n");
		return 0;
	}
	for(i = 1; i <= m; i++) {
		scanf("%d%d%d",&n1,&n2,&vl);
		e[n1].pb(n2);
		e[n2].pb(n1);
		cap[n1][n2] += vl;
		cap[n2][n1] += vl;
	}

	printf("%d\n",cauta(0,tmax - 1));

	return 0;
}