#include <cstdio>

const int N_MAX = 51;
const int M_MAX = 300;
const int T_MAX = 102;
const int E_MAX = 4 * M_MAX * T_MAX;
const int D = N_MAX*T_MAX - 1;

struct muchie {
	int x,y,c;
	muchie ( int a, int b, int cap ) { x = a; y = b; c = cap; };
};

int n,m;
int v[N_MAX];
int a[N_MAX], b[N_MAX], c[N_MAX];
vector<muchie> ed;
int destStart;
vector<int> G[N_MAX * T_MAX];
int back[N_MAX * T_MAX];

inline void addEdge ( int a, int b, int c ) {
	G[a].push_back(ed.size()); ed.push_back(muchie(a,b,c));
	G[b].push_back(ed.size()); ed.push_back(muchie(b,a,0));
}

int BF() {
	queue<int> Q;
	memset(back,-1,sizeof(back));
	for (Q.push(0); !Q.empty() && back[D] == -1; Q.pop()) {
		for (int i = 0; i < G[Q.front()].size(); ++i) {
			int edge = G[Q.front()][i];
			
		}
	}
}

void flux() {
	int f = 0, aux;
	do {
		aux = BF();
		f += aux;
	} while (aux);
	return f;
}

void reset_graph() {
	for (int i = 0; i < ed.size(); i += 2) {
		ed[i].c = ed[i].c + ed[i+1].c;
		ed[i+1].c = 0;
	}
}

bool ok ( int t ) {
	destEdge = destStart + 2*(t-1);
	ed[destEdge].c = sum;
	flux();
	bool ret = ed[destEdge^1].c == sum;
	reset_graph();
	return ret;
}

int bsearch() {
	int t = 0;
	for (int step = 1 << 7; step; step >>= 1)
		if (t + step < T_MAX && !ok(t + step))
			t += step;
	return t+1;
}

int main() {
	freopen("algola.in","rt",stdin);
	freopen("algola.out","wt",stdout);
	scanf("%d %d",&n,&m);
	for (int i = 1; i <= n; ++i) scanf("%d",&v[i]);
	sum = 0;
	for (int i = 1; i <= n; ++i) sum += v[i];
	if (sum == v[1]) {
		printf("0\n");
		return 0;
	}
	
	for (int i = 0; i < m; ++i) {
		scanf("%d %d %d",&a[i],&b[i],&c[i]);
		addEdge(a[i], b[i]+n, c[i]);
		addEdge(b[i], a[i]+n, c[i]);
	}
	for (int k = 1; k < T_MAX; ++k) {
		for (int i = 0; i < m; ++i) {
			addEdge(a[i] + k*n, b[i] + k*n + n, c[i]);
			addEdge(b[i] + k*n, a[i] + k*n + n, c[i]);
		}
	}
	for (int i = 1; i <= n; ++i) addEdge(0, i, v[i]);
	destStart = ed.size();
	for (int i = 0; i < T_MAX; ++i) addEdge(i*n+1, D, 0);

	printf("%d\n",bsearch());
	return 0;
}