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

#define pb push_back
#define mp(i,j) make_pair(i,j)
#define inf 20000
#define nm 55
#define tm 100

using namespace std;

int n,m,x,n1,n2,cp,tot,prev[tm * nm];
short int cap[nm][tm][nm][tm],fl[nm][tm][nm][tm],pcap[nm][nm];
vector <short int> e[nm];
pair <int,int> st[tm * nm];
char v[nm][tm];

int drum(int x) {
	memset(v,0,sizeof(v));
	int p = 1, q = 1,bun = 0;
	st[1] = mp(0,0);
	v[0][0] = 1;
	prev[1] = -1;
	while(q <= p) {
		int nn = st[q].first;
		int nt = st[q].second;
		for(int i = 0; i < (int)e[nn].size(); i++) {
			int gn = e[nn][i];
			int gt = nt + 1;
			if(gt <= x && !v[gn][gt] && cap[nn][nt][gn][gt] > fl[nn][nt][gn][gt]) {
				v[gn][gt] = 1;
				st[++p] = mp(gn,gt);
				prev[p] = q;
				if(gn == 1 && gt == x) {
					bun = 1;
					break;
				}
			}
			gt = nt - 1;
			if(gt >= 0 && !v[gn][gt] && cap[nn][nt][gn][gt] > fl[nn][nt][gn][gt]) {
				v[gn][gt] = 1;
				st[++p] = mp(gn,gt);
				prev[p] = q;
				if(gn == 1 && gt == x) {
					bun =  1;
					break;
				}
			}
		}
		if(bun) break;
		q++;
	}
	if(!bun) return 0;
	else {
		int v = p,add = inf;
		while(prev[v] != -1) {
			int cn = st[v].first;
			int ct = st[v].second;
			int pn = st[prev[v]].first;
			int pt = st[prev[v]].second;
			int val = cap[pn][pt][cn][ct] - fl[pn][pt][cn][ct];
			add = min(add,val);
			v = prev[v];
		}
		v = p;
		while(prev[v] != -1) {
			int cn = st[v].first;
			int ct = st[v].second;
			int pn = st[prev[v]].first;
			int pt = st[prev[v]].second;
			fl[pn][pt][cn][ct] += add;
			fl[cn][ct][pn][pt] = - fl[pn][pt][cn][ct];
			v = prev[v];
		}
		return 1;
	}
}

int flux(int x) {
	memset(fl,0,sizeof(fl));
	while(drum(x)) ;
	int r = 0;
	for(int i = 1; i <= n; i++) r += fl[i][x - 1][1][x];
	return r;
}

int bun(int x) {
	int j = flux(x + 1);
	if(j == tot) return 1;
	else return 0;
} 

int cauta(int f,int l) {
	int r = 0;
	while(f <= l) {
		int m = (f + l) / 2;
		if(bun(m)) {
			l = m - 1;
			r = m;
		}
		else f = m + 1;
	}
	return r;
}

void capacities() {
	for(int x = 0; x < tm - 3; x++) 
		for(int i = 1; i <= n; i++) 
			for(int j = 0; j < (int)e[i].size(); j++) 
				cap[i][x][e[i][j]][x + 1] = pcap[i][e[i][j]];
}

int main() {
	freopen("algola.in","r",stdin);
	freopen("algola.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++) {
		scanf("%d",&x);
		e[0].pb(i);
		tot += x;
		cap[0][0][i][1] = x;
		pcap[i][i] = inf;
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) e[i].pb(j);

	for(int i = 1; i <= m; i++) {
		scanf("%d%d%d",&n1,&n2,&cp);		
		pcap[n1][n2] = pcap[n2][n1] = cp;	
	}

	capacities();
	int t = cauta(1,tm);

	printf("%d\n",t);

	return 0;
}