#include <cstdio>
#include <vector>

using namespace std;

#define pb(v, a) v.push_back(a)
#define sz(a) a.size()

#define Nmax 105
#define Tmax 305
#define Mmax 405

int A[Nmax], n, m1[Mmax], m2[Mmax], cost[Mmax], rez, flux, m, dest, T[Nmax*Tmax], viz[Nmax*Tmax], Q[Nmax*Tmax], F[Nmax];
vector< vector<int> > vec, c, f;

void readdata()
{
	freopen("algola.in", "r", stdin);
	freopen("algola.out", "w", stdout);
	
	int i;
	
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; ++i)
		scanf("%d", &A[i]);
	for (i = 0; i < m; ++i)
	{
		scanf("%d %d %d", &m1[i], &m2[i], &cost[i]);
		--m1[i]; --m2[i];
	}
}

int capacitate(int a, int b)
{
	int i;
	for (i = 0; i < sz(vec[a]); ++i)
		if (vec[a][i] == b)
			return c[a][i];
}

int fluxul(int a, int b)
{
	int i;
	for (i = 0; i < sz(vec[a]); ++i)
		if (vec[a][i] == b)
			return f[a][i];	
}

int bfs()
{
	int i, cont = 0, cap = 1, nod;
	
	memset(viz, 0, sizeof(viz));
	memset(T, 0xFF, sizeof(T));
		
	for (i = 1; i < n; ++i)
		if (A[i]-F[i])
		{
			Q[++cont] = i;
			viz[i] = 1;
		}
	while (cap <= cont)
	{
		nod = Q[cap];
		for (i = 0; i < sz(vec[nod]); ++i)
			if (!viz[vec[nod][i]] && (c[nod][i] - f[nod][i] > 0))
			{
				Q[++cont] = vec[nod][i];
				T[vec[nod][i]] = nod;
				viz[vec[nod][i]] = 1;
				if (vec[nod][i] == dest) return 1;
			}
		++cap;
	}
	return 0;
}

void modif(int a, int b, int s)
{
	int i;
	for (i = 0; i < sz(vec[a]); ++i)
		if (vec[a][i] == b)
		{
			f[a][i] += s;
			return;
		}
}

void solve()
{
	int i, n1, n2, r, poz, sum = 0;
	
	A[0] = 0;
	for(i = 1; i < n; ++i) sum += A[i];
	
	vec.resize(Nmax*Tmax);
	c.resize(Nmax*Tmax);
	f.resize(Nmax*Tmax);
	
	while (flux < sum)
	{
		//build graf
		for (i = 0; i < m; ++i)
		{
			n1 = m1[i] + rez*n;
			n2 = m2[i] + (rez+1)*n;
			pb(vec[n1], n2); pb(c[n1], cost[i]); pb(f[n1], 0);
			pb(vec[n2], n1); pb(c[n2], 0); pb(f[n2], 0);			
			
			n1 = m2[i] + rez*n;
			n2 = m1[i] + (rez+1)*n;
			pb(vec[n1], n2); pb(c[n1], cost[i]); pb(f[n1], 0);
			pb(vec[n2], n1); pb(c[n2], 0); pb(f[n2], 0);					
		}
		for (i = 0; i < n; ++i)
		{
			n1 = i + rez*n;
			n2 = i + (rez+1)*n;
			pb(vec[n1], n2); pb(c[n1], cost[i]); pb(f[n1], 0);
			pb(vec[n2], n1); pb(c[n2], 0); pb(f[n2], 0);						
		}
		dest = (rez+1)*n;
		
		while (bfs())
		{
			for (i = rez*n; i < (rez+1)*n; ++i)
			{
				if (!viz[i] || (capacitate(i, dest) <= fluxul(i, dest)) ) continue;
				
				r = capacitate(i, dest) - fluxul(i, dest);
				for (poz = i; T[poz] > -1; poz = T[poz])
					r = min(r, capacitate(T[poz], poz) - fluxul(T[poz], poz));
				r = min(r, A[poz]-F[poz]);
				if (r == 0) continue;
				
				flux += r;
				
				modif(i, dest, r); modif(dest, i, -r);
				for (poz = i; T[poz] > -1; poz = T[poz])
				{
					modif(T[poz], poz, r);
					modif(poz, T[poz], -r);
				}
				F[poz] += r;
			}
		}
		++rez;
	}
	printf("%d\n", rez);
}

int main()
{
	readdata();
	solve();
	return 0;
}