#include <cstdio>
#include <cstdlib>
#include <vector>
#define maxn 54
#define maxp 5510
#define inf 0x3f3f3f3f

using namespace std;

int n, m, i, j, src, dst, suma, a, b, cc;
int v[maxn];
vector <int> g[maxn], tt[maxn];
vector <int> x[maxp];
char c[maxp][maxp];
int flux[maxp], up[maxp];
int sol, ok;

void build_graph() {
	int t, fiu;

	memset(c, 0, sizeof(c));
	src = 0; dst = 1;
	for (t = 100; t > 0; t--) {
		for (i = 1; i <= n; i++) {
			x[t * n + i].push_back((t - 1) * n + i);
			x[(t - 1) * n + i].push_back(t * n + i);
			x[t * n + i].push_back(src);

			for (j = 0; j < g[i].size(); j++) {
				fiu = g[i][j];
				x[t * n + i].push_back((t - 1) * n + fiu);
				x[(t - 1) * n + fiu].push_back(t * n + i);
			}
		}
	}
}

inline int min(int a, int b) {
	if (a < b)
		return a;
	return b;
}

inline void build(int t) {
	int i, j, k, fiu;
	x[src].clear();

	for (k = 100; k > 0; k--)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				c[k * n + i][(k - 1) * n + j] = c[(k - 1) * n + j][k * n + i] = 0; 
	for (i = 0; i <= 100 * n; i++)
		c[0][i] = c[i][0] = 0;

	for (i = 1; i <= n; i++) {
		x[src].push_back(t * n + i);
		c[src][t * n + i] = v[i];
	}

	for (k = t; k > 0; k--) {
		for (i = 1; i <= n; i++) {
			c[k * n + i][(k - 1) * n + i] = inf;
			for (j = 0; j < g[i].size(); j++) {
				fiu = g[i][j];
				c[k * n + i][(k - 1) * n + fiu] = tt[i][j];
			}
		}	
	}
}

inline void init() {
//	memset(up, -1, sizeof(up));
	memset(flux, 0, sizeof(flux));
	flux[src] = inf;
}

inline int bf() {
	int p, u;
	int nod, fiu;
	int q[maxp];

	p = u = 1;
	q[u] = src;

	while (p <= u) {
		nod = q[p];

		for (i = 0; i < x[nod].size(); i++) {
			fiu = x[nod][i];

			if (flux[fiu] == 0 && c[nod][fiu] > 0) {
				flux[fiu] = min(flux[nod], c[nod][fiu]);
				q[++u] = fiu;
				up[fiu] = nod;
				if (fiu == dst) {
					p = u + 1;
					break;
				}
			}
		}

		p++;
	}


	if (flux[dst] == 0) {
		ok = 0;
		return 0;
	}

	ok = 1;
	for (i = dst; i != src; i = up[i]) {
		c[up[i]][i] -= flux[dst];
		c[i][up[i]] += flux[dst];
	}

	return flux[dst];
}

inline bool posibil(int t) {
	int ff, i;
	build(t);

	ok = 1; ff = 0;
	while (ok) {
		init();
		ff += bf();
		if (ff == suma)
			break;
	}

/*	for (i = 1; i <= n; i++) 
		x[t * n + i].pop_back();*/

//	fprintf(stderr, "%d  %d %d\n", t, ff, suma);

	if (ff >= suma)
		return true;
	return false;
}

void bsearch(int left, int right) {
	int m;
	while (left <= right) {
		m = (left + right) / 2;
		if (posibil(m)) {
			sol = min(sol, m);
			right = m - 1;
		}
		else
			left = m + 1;
	}
}

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

	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
		suma += v[i];
	}

//	printf("%d\n", suma);

	for (i = 1; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &cc);
		g[a].push_back(b);
		tt[a].push_back(cc);

		g[b].push_back(a);
		tt[b].push_back(cc);
	}

	build_graph();

	sol = inf;
	bsearch(1, 100);
	
	printf("%d\n", sol);

	return 0;
}