#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 60;
const int MAXM = 310;
const int MAXT = 101;
const int MAXE = 4 * MAXM * MAXT;
const int MAXV = MAXN * MAXT;
const int S = 0;
const int D = 1;
const int INF = 100000000;

#define ii pair <int, int>

int N, M, E, L, Sum, Sol;
int X[MAXE], Y[MAXE], C[MAXE], auxC[MAXE];
vector <int> A[MAXV];
int Q[MAXV], From[MAXV];

int BFS()
{
	memset(From, -1, sizeof(From));
	L = 1;
	Q[L] = S;
	From[S] = INF;

	for (int i = 1; i <= L; ++i)
		for (size_t j = 0; j < A[Q[i]].size(); ++j)
		{
			int much = A[Q[i]][j];

			if (From[Y[much]] == -1 && C[much] > 0)
			{
				Q[++L] = Y[much];
				From[Q[L]] = much;

				if (Q[L] == D) break;
			}
		}

	if (From[D] == -1) return 0;

	int f = INF;

	for (int i = From[D]; i != INF; i = From[X[i]]) f = min(f, C[i]);
	for (int i = From[D]; i != INF; i = From[X[i]]) 
	{
		C[i] -= f;
		if (i&1) C[i+1] += f;
		else C[i-1] += f;
	}

	return f;
}

int flux()
{
	int res = 0, aux;

	do
	{
		aux = BFS();
		res += aux;
	}
	while (aux);

	return res;
}

int works(int T)
{
	memcpy(C, auxC, sizeof(auxC));

	for (int i = 1; i <= N; ++i)
	{
		Y[2*i-1] = T*N + i;
		X[2*i] = T*N + i;
		A[X[2*i]].push_back(2*i);
	}

	return flux() == Sum;
}

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

	fin >> N >> M;

	for (int i = 1; i <= N; ++i) 
	{
		int c;
		fin >> c;
		
		Sum += c;
		X[++E] = S, C[E] = c;
		A[X[E]].push_back(E);
		Y[++E] = S, C[E] = 0;
	}

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

		for (int time = 1; time < MAXT; ++time) 
		{
			X[++E] = time*N + x, Y[E] = (time-1)*N + y, C[E] = c;
			A[X[E]].push_back(E);
			X[++E] = (time-1)*N + y, Y[E] = time*N + x, C[E] = 0;
			A[X[E]].push_back(E);

			X[++E] = time*N + y, Y[E] = (time-1)*N + x, C[E] = c;
			A[X[E]].push_back(E);
			X[++E] = (time-1)*N + x, Y[E] = time*N + y, C[E] = 0;
			A[X[E]].push_back(E);
		}
	}

	for (int i = 1; i <= N; ++i)
		for (int time = 1; time < MAXT; ++time)
		{
			X[++E] = time*N + i, Y[E] = (time-1)*N + i, C[E] = INF;
			A[X[E]].push_back(E);
			X[++E] = (time-1)*N + i, Y[E] = time*N + i, C[E] = 0;
			A[X[E]].push_back(E);
		}

	int front = 0, middle, back = MAXT - 1;
	memcpy(auxC, C, sizeof(C));

	while (front <= back)
	{
		middle = (front + back) / 2;

		if (works(middle)) 
		{
			back = middle - 1;
			Sol = middle;
		}
		else front = middle + 1;
	}

	fout << Sol << endl;

	return 0;
}