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

#define pb push_back
#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
#define usi unsigned short int

const int MAX_N = 54;
const int MAX_P = 5520;
const int INF = 0x3f3f3f3f;

usi n, m, s;
usi a[MAX_N];
vector <usi> gi[MAX_N], cc[MAX_N], g[MAX_P];
usi c[MAX_P][MAX_P], f[MAX_P], up[MAX_P], q[MAX_P];

inline usi min(usi a, usi b) { return (a < b) ? a : b; }

inline usi bf()
{
	memset(f, 0, sizeof(f));
	f[0] = INF;

	q[0] = 0;

	usi l, r;

	for (l = r = 0; l <= r; ++l)
	{
		usi nod = q[l];

		forit(it, g[nod])
			if (!f[*it] && c[nod][*it])
			{
				f[*it] = min(f[nod], c[nod][*it]);
				q[++r] = *it;
				up[*it] = nod;

				if (*it == 1)
				{
					l = r + 1;
					break;
				}
			}
	}

	if (!f[1]) return 0;

	for (int i = 1; i; i = up[i])
	{
		c[up[i]][i] -= f[1];
		c[i][up[i]] += f[1];
	}

	return 1;
}

inline usi check(usi t)
{
	int i, j, k;

//initialize step

	g[0].clear();

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

	for (i = 0; i <= 100 * n; ++i)
		c[0][i] = c[i][0] = 0;

	for (i = 1; i <= n; ++i)
	{
		g[0].pb(t * n + i);
		c[0][t * n + i] = a[i];
	}

	for (i = t; i; --i)
		for (j = 1; j <= n; ++j)
		{
			c[i * n + j][(i - 1) * n + j] = INF;

			for (k = 0; k < gi[j].size(); ++k)
				c[i * n + j][(i - 1) * n + gi[j][k]] = cc[j][k];
		}
//

	int q = 1, sum = 0;
	for (; sum != s && q; q = bf(), sum += f[1]);

	if (sum >= s) return 1;
	return 0;

}

inline usi bin(usi st, usi dr)
{
	usi ret = 0;

	while (st <= dr)
	{
		usi mij = (st + dr) >> 1;

		if (check(mij)) ret = mij, dr = mij - 1;
		else st = mij + 1;
	}

	return ret;
}

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

	scanf("%hu %hu", &n, &m);

	for (i = 1; i <= n; ++i)
	{
		scanf("%hu", &a[i]);
		s += a[i];
	}

	for (i = 1; i <= m; ++i)
	{
		usi n1, n2, cap;

		scanf("%hu %hu %hu", &n1, &n2, &cap);

		gi[n1].pb(n2);
		gi[n2].pb(n1);

		cc[n1].pb(cap);
		cc[n2].pb(cap);
	}

//initialize

	for (i = 100; i; --i)
		for (j = 1; j <= n; ++j)
		{
			g[i * n + j].pb((i - 1) * n + j);
			g[(i - 1) * n + j].pb(i * n + j);
			g[i * n + j].pb(0);

			forit(it, gi[j])
			{
				g[i * n + j].pb((i - 1) * n + *it);
				g[(i - 1) * n + *it].pb(i * n + j);
			}
		}
//
	
	printf("%hu\n", bin(1, 100));
}