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

using namespace std;

#define lg 5252
#define N 52
#define pb push_back

int n, m, x, y, z, i, j, t, rsp, flux, prd[lg], init[N][N], cnt[N], tot;
bool fst[lg];
char cp[lg][lg];
vector<int> v[N];

int baga(int i, int j){
	return j * 51 + i;
}

int find(){
	int i, nxt, t, x, y, found = 0, mn = 150;

	memset(fst, 0, sizeof(fst)); memset(prd, 0xff, sizeof(prd));
	queue<int> q;
	fst[0] = 1;
	q.push(0);

	while (!q.empty() && !found){
		y = q.front(), q.pop();

		t = y / 51, x = y % 51;

		//if (rsp > 2)
		//printf("%d: \n", x);

		for (i = 0; i < (int)v[x].size(); i ++){
			nxt = baga(v[x][i], t + 1);

			//if (rsp > 2)
			//printf("  %d %d\n", v[x][i], (int)cp[y][nxt]);

			if (!fst[nxt] && cp[y][nxt] > 0 && t + 1 <= rsp){
				fst[nxt] = 1;
				prd[nxt] = y;

				q.push(nxt);

				if (v[x][i] == 1){
					found = nxt;
					break ;
				}
			}

			nxt = baga(v[x][i], t - 1);
			if (!fst[nxt] && cp[y][nxt] > 0 && t - 1 > 0){
				fst[nxt] = 1;
				prd[nxt] = y;

				q.push(nxt);

				if (v[x][i] == 1){
					found = nxt;
					break;
				}
			}
		}

		//printf("%d\n", t); fflush(stdout);
		nxt = baga(x, t + 1);
		if (!fst[nxt] && t + 1 <= rsp){
			fst[nxt] = 1;
			prd[nxt] = y;

			q.push(nxt);
		}
	
	}

	if (!found)
		return 0;

	for (x = found; prd[x] != -1; x = prd[x]){
		mn = min(mn, (int)cp[ prd[x] ][x]);

		//if ((int)cp[ prd[x] ][x] == 0)
		//	printf("asta %d %d\n", prd[x] % 51, x % 51);
	}

	for (; prd[found] != -1; found = prd[found]){
		cp[ prd[found] ][found] -= mn;
		cp[found][ prd[found] ] += mn;
	}

	//printf("da %d %d\n", rsp, mn);

	flux += mn;

	return mn;
}

int main()
{
	freopen("algola.in", "rt", stdin);
	freopen("algola.out", "wt", stdout);

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

		tot += cnt[i];
	}

	for (i = 1; i <= m; i ++){
		scanf("%d%d%d", &x, &y, &z);

		v[x].pb(y); v[y].pb(x);

		init[x][y] = init[y][x] = max(init[x][y], z);
	}

	for (i = 1; i <= n; i ++)
		for (t = 0; t <= 100; t ++){
			x = baga(i, t); y = baga(i, t + 1);

			cp[x][y] = 100;

			for (j = 0; j < (int)v[i].size(); j ++)
				cp[ baga(i, t) ][ baga(v[i][j], t + 1) ] = init[i][ v[i][j] ];
		}
	for (i = 1; i <= n; i ++){
		v[0].pb(i); v[i].pb(0);

		cp[ baga(0, 0) ][ baga(i, 1) ] = cnt[i];
	}

	//printf("%d\n", (int)cp[ baga(2, 1) ][ baga(1, 2) ]);

	for (rsp = 1; flux < tot; rsp ++)
		while (find());


	printf("%d\n", rsp - 2);

	return 0;
}