#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int N_MAX = 50;
const int M_MAX = 300;
const int T_MAX = 100;
const int NODURI = N_MAX*(T_MAX+1) + 2;
const int D = NODURI - 1;
const int INF = 0x3f3f3f3f;

struct muchie {
	int x,y,c;
	muchie ( int a, int b, int cap ) { x = a; y = b; c = cap; };
};

int n,m;
int v[N_MAX];
int a[M_MAX], b[M_MAX], c[M_MAX];
int sum;
vector<muchie> ed;
int destStart;
vector<int> G[NODURI];
int back[NODURI];

inline void addEdge ( int a, int b, int c ) {
	G[a].push_back(ed.size()); ed.push_back(muchie(a,b,c));
	G[b].push_back(ed.size()); ed.push_back(muchie(b,a,0));
}

int BF() {
	queue<int> Q;
	memset(back,-1,sizeof(back));
	back[0] = INF;
	for (Q.push(0); !Q.empty() && back[D] == -1; Q.pop()) {
		for (int i = 0; i < G[Q.front()].size(); ++i) {
			int edge = G[Q.front()][i];
			if (back[ed[edge].y] == -1 && ed[edge].c > 0) {
				back[ed[edge].y] = edge;
				Q.push(ed[edge].y);
				if (ed[edge].y == D) break;
			}
		}
	}
	if (back[D] == -1) return 0;
	int f = INF;
	for (int i = back[D]; i != INF; i = back[ed[i].x])
		if (f > ed[i].c)
			f = ed[i].c;
	for (int i = back[D]; i != INF; i = back[ed[i].x]) {
		ed[i].c -= f;
		ed[i^1].c += f;
	}
	return f;
}

int flux() {
	int f = 0, aux;
	do {
		aux = BF();
		f += aux;
	} while (aux);
	return f;
}

void reset_graph() {
	for (int i = 0; i < ed.size(); i += 2) {
		ed[i].c = ed[i].c + ed[i+1].c;
		ed[i+1].c = 0;
	}
}

bool ok ( int t ) {
	int destEdge = destStart + 2*t;
	ed[destEdge].c = sum;
	int f = flux();
	bool ret = f == sum;
	reset_graph();
	ed[destEdge].c = 0;
	return ret;
}

int bsearch() {
	int t = 0;
	for (int step = 1 << 7; step; step >>= 1)
		if (t + step <= T_MAX && !ok(t + step))
			t += step;
	return t+1;
}

int main() {
	freopen("algola.in","rt",stdin);
	freopen("algola.out","wt",stdout);
	scanf("%d %d",&n,&m);
	for (int i = 1; i <= n; ++i) scanf("%d",&v[i]);
	sum = 0;
	for (int i = 1; i <= n; ++i) sum += v[i];
	if (sum == v[1]) {
		printf("0\n");
		return 0;
	}
	
	for (int i = 0; i < m; ++i) {
		scanf("%d %d %d",&a[i],&b[i],&c[i]);
		addEdge(a[i], b[i]+n, c[i]);
		addEdge(b[i], a[i]+n, c[i]);
	}
	for (int i = 1; i <= n; ++i) addEdge(i, i + n, INF);
	for (int k = 1; k < T_MAX; ++k) {
		for (int i = 0; i < m; ++i) {
			addEdge(a[i] + k*n, b[i] + k*n + n, c[i]);
			addEdge(b[i] + k*n, a[i] + k*n + n, c[i]);
		}
		for (int i = 1; i <= n; ++i) addEdge(k*n + i, k*n + i + n, INF);
	}
	for (int i = 1; i <= n; ++i) addEdge(0, i, v[i]);
	destStart = ed.size();
	for (int i = 0; i <= T_MAX; ++i) addEdge(i*n+1, D, 0);

	printf("%d\n",bsearch());
	return 0;
}