#include <fstream>
#include <iostream>
#include <numeric>
#include <array>
#include <vector>
#include <queue>
using namespace std;

constexpr int maxt = 110, maxn = 50, maxsz = (maxt+1) * maxn + 10, inf = 51, dest = maxsz-1;
constexpr int surs = 0;

struct muc { int surs, dest, cap; };
struct com { int timp, nod; };

int encode(const int timp, const int nod){
	return (timp+1) * maxn + nod + 1; }

int encode(const int nod){
	return nod+1; }

vector<vector<int> > graf(maxsz);
array<array<int, maxsz>, maxsz> cap, flux = {};
array<int, maxsz> tata;
queue<int> de_viz;

void bfs(){
	while(!de_viz.empty()){
		const int cur = de_viz.front();
		de_viz.pop();
		if(cur != dest){
			for(const auto next : graf[cur]){
				if(cap[cur][next] > flux[cur][next] && tata[next] == -1){
					tata[next] = cur;
					de_viz.push(next); } } } } }

int flux_max(){
	int delta = 0;
	while(true){
		fill(begin(tata), end(tata), -1);
		de_viz.push(surs);

		bfs();
		if(tata[dest] == -1){
			return delta; }

		for(const auto leaf : graf[dest]){
			if(tata[leaf] != -1 && cap[leaf][dest] > flux[leaf][dest]){
				tata[dest] = leaf;
				int rezid = inf;
				for(int x = dest; x != surs; x = tata[x]){
					rezid = min(rezid, cap[tata[x]][x] - flux[tata[x]][x]); }
				if(rezid > 0){
					for(int x = dest; x != surs; x = tata[x]){
						flux[tata[x]][x] += rezid;
						flux[x][tata[x]] -= rezid; }
					delta += rezid; } } } } }


void draw_muc(const int a, const int b, const int c){
	graf[a].push_back(b);
	graf[b].push_back(a);
	cap[a][b] = c;
	cap[b][a] = 0; }

int main(){
	ifstream f("algola.in");
	ofstream g("algola.out");

	int n, m;
	f >> n >> m;
	vector<int> nr_oameni(n, 0);
	for(auto& x : nr_oameni){
		f >> x; }
	nr_oameni[0] = 0;

	const int flux_final = accumulate(begin(nr_oameni)+1, end(nr_oameni), 0);

	vector<muc> muchii(m);
	for(auto& x : muchii){
		f >> x.surs >> x.dest >> x.cap;
		--x.surs, --x.dest; }


	if(flux_final == 0){
		g << 0;
		return 0; }


	for(int i = 1; i < n; ++i){
		draw_muc(surs, encode(i), nr_oameni[i]); }
	draw_muc(encode(0, 0), dest, inf);

	int t = 1, flux_cur = 0;
	for( ; t < maxt; ++t){
		for(int i = 1; i < n; ++i){
			draw_muc(encode(i), encode(t-1, i), inf); }
		draw_muc(encode(t, 0), dest, inf);

		for(const auto x : muchii){
			draw_muc(encode(t-1, x.surs), encode(t, x.dest), x.cap);
			draw_muc(encode(t-1, x.dest), encode(t, x.surs), x.cap); }

		flux_cur += flux_max();
		if(flux_cur == flux_final){
			break; } }
	g << t;
	return 0; }