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

using namespace std;

#define pb push_back
#define usi unsigned short int

#define MAX_N 64
#define MAX_G 8192
#define inf 32000

int n, m, p, q, dest, lim;
int tata[MAX_G], Q[MAX_G];
usi A[MAX_N], flux[MAX_G];
usi cost, flow, improve, sol;

vector <int> v[MAX_G];
vector <usi> c[MAX_G], aux[MAX_G];

void cit() {
	freopen("algola.in", "r", stdin);
	freopen("algola.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%hd", &A[i]);
		A[0] += A[i];
	
		v[1].pb(i + 1);
		c[1].pb(A[i]); aux[1].pb(A[i]);
	}

	dest = 2 * n * n + 2;	
	for (int i = 1; i <= m; i++) {
    	scanf("%d %d %hd", &p, &q, &cost);
		p++; q++;

		if (p != q)
			for (int T = 1; T <= 2 * n; T++) {
				if (q + n <= dest) {
	        		v[p].pb(q + n); 
					c[p].pb(cost); aux[p].pb(cost);

					v[q + n].pb(p);
					c[q + n].pb(0); aux[q + n].pb(0);
				}
				
				if (p + n <= dest) {
					v[q].pb(p + n);
					c[q].pb(cost); aux[q].pb(cost);
			
					v[p + n].pb(q);
					c[p + n].pb(0); aux[p + n].pb(0);
				}
				p += n; q += n;
			}
	}

	for (int i = 1; i <= n; i++)
		for (int T = 1; T <= 2 * n; T++)
			if (T * n + i + 1 <= dest) {
				v[(T - 1) * n + i + 1].pb(T * n + i + 1);	
				c[(T - 1) * n + i + 1].pb(inf); aux[(T - 1) * n + i + 1].pb(inf);

				v[T * n + i + 1].pb((T - 1) * n + i + 1);
				c[T * n + i + 1].pb(0); aux[T * n + i + 1].pb(0);
			} 
}

void bfs(int val) {
	memset(tata, 0, sizeof(tata));
	memset(flux, 0, sizeof(flux));

	Q[1] = 1; flux[1] = inf; improve = 0;

	int st = 0, dr = 1;
	while (st < dr) {
    	st++;

		int nod = Q[st], len = v[Q[st]].size();
		for (int i = 0; i < len; i++)
			if (v[nod][i] >= val && !flux[v[nod][i]] && c[nod][i] > 0) {
            	int x = flux[nod];
				if (c[nod][i] < x) x = c[nod][i];

				flux[v[nod][i]] = x;
				tata[v[nod][i]] = nod;
				Q[++dr] = v[nod][i];

				if (flux[dest]) break;
			}
		if (flux[dest]) break;
	}
	
	improve = flux[dest];
	if (!improve) return;

	int x = dest;
	while (x != 1) {
    	int len = v[tata[x]].size();
		for (int i = 0; i < len; i++)
			if (v[tata[x]][i] == x) {
            	c[tata[x]][i] -= improve;
				break;
			}

		len = v[x].size();
        for (int i = 0; i < len; i++)
            if (v[x][i] == tata[x]) {
                c[x][i] += improve;
                break;
            }
		x = tata[x];
	}

	flow += improve;
}

void get_graph(int poz) {
	for (int i = 1; i <= dest; i++) {
    	int len = c[i].size();
		for (int j = 0; j < len; j++)
			c[i][j] = aux[i][j];
	}
		
	for (int i = 0; i < n; i++)
		v[1][i] = poz + i;
}

void solve() {
	if (A[1] == A[0]) {
    	printf("0\n");
		return;
	}

	sol = inf;
    int st = 0, dr = 2 * n + 1, mid = 0;
	while (st + 1 < dr) {
    	mid = (st + dr) / 2;

		get_graph(dest - n * mid);

		improve = 1; flow = 0;
		while (improve)
        	bfs(mid);

		if (flow == A[0]) {
        	if (mid < sol) sol = mid;
			dr = mid;
		}
		else st = mid;
	}

	printf("%hd\n", sol);	
}

int main() {

	cit();
	solve();
		
	return 0;
}