#include <fstream>
#include <vector>

using namespace std;

#define foreach(V) for(vector<pair<int, int> >::iterator it = (V).begin(); it != (V).end(); ++it)

const int MAX_N = 55;
const int MAX_T = 5505;
const int INF = 0x3f3f3f3f;

ifstream fin ("algola.in");
ofstream fout ("algola.out");

int S, D, N, M, A[MAX_N], K, T[MAX_T];
char F[MAX_T][MAX_T], C[MAX_T][MAX_T];

char viz[MAX_T];

vector <pair<int, int> > L[MAX_N];
vector <int> G[MAX_T];

void citire()
{
	fin >> N >> M;

	for(int i = 1; i <= N; ++i)
	{
		fin >> A[i];
		K += A[i];
	}

	for(int i = 1; i <= M; ++i)
	{
		int x, y, c;
		fin >> x >> y >> c;

		L[x].push_back(make_pair(y, c));
		L[y].push_back(make_pair(x, c));
	}
}

bool bfs()
{
	int Q[MAX_T];
	memset(viz, 0, sizeof viz);

	Q[0] = 1; Q[1] = 0;
	viz[0] = 1;

	for(int i = 1; i <= Q[0]; ++i)
	{
		int nod = Q[i];

		if(nod == D) continue;

		for(size_t j = 0; j < G[nod].size(); ++j)
		{
			int act = G[nod][j];

			if(viz[act] || F[nod][act] == C[nod][act]) continue;

			viz[act] = 1;
			Q[++Q[0]] = act;
			T[act] = nod;
		}
	}

	return viz[D];
}

bool check(int P)
{
	memset(F, 0, sizeof F);
	memset(C, 0, sizeof C);

	for(int i = 0; i < MAX_T; ++i)
		G[i].clear();

	int t = P+1;
	for(int i = 1; i <= N; ++i)
	if(A[i])
	{
		C[0][t*i] = A[i];
		G[0].push_back(t*i);
		G[t*i].push_back(0);
	}

	for(int i = 1; i <= N; ++i)
		for(int k = 0; k < P; ++k)
		{
			foreach(L[i])
			{
				int j = it -> first;
				int c = it -> second;
				C[t*i + k][t*j + k+1] = c;

//				if(j == N && k+1 == P)
//					printf("%d %d\n", i, k);
				
				G[t*i + k].push_back(t*j + k+1);
				G[t*j + k+1].push_back(t*i + k);	
			}

			C[t*i + k][t*i + k+1] = INF;
			G[t*i + k].push_back(t*i + k+1);
			G[t*i + k+1].push_back(t*i + k);
		}

	D = t + P;
//	printf("%d\n", G[D].size());

	int flow = 0, fmin;

	while(bfs())
		for(size_t i = 0; i < G[D].size(); ++i)
		{
			int nod = G[D][i];

			if(F[nod][D] == C[nod][D] || viz[nod] == 0) continue;

			fmin = INF;
			for(int i = D; i; i = T[i])
				fmin = min(fmin, C[T[i]][i] - F[T[i]][i]);

			for(int i = D; i; i = T[i])
				F[T[i]][i] += fmin,
				F[i][T[i]] -= fmin;

			flow += fmin;
		}

//	printf("%d\n", flow);
	return (flow >= K);
}

int main()
{
	citire();

	int i = 100;
	for(int lg = (1 << 7); lg; lg >>= 1)
		if(i - lg >= 0 && check(i - lg))
			i -= lg;

	//check(2);

	fout << i;
}