#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef vector<ll> vll;
typedef vector<vll> vvll;
const ll INF = 1LL << 60;

struct MCMF {
	int N;
	vll found, dad, dist, pi;
	vvll cap, flow, cost;

	MCMF(int N): N(N), cap(N, vll(N)), flow(cap), cost(cap),
	dad(N), found(N), pi(N), dist(N+1) {};

	void add_edge(int from, int to, ll ca, ll co) {
		cap[from][to] = ca; cost[from][to] = co;
	}
	bool search(int source, int sink) {
		fill(found.begin(), found.end(), 0);
		fill(dist.begin(), dist.end(), INF);
		dist[source] = 0;
		while(source != N) {
			int best = N;
			found[source] = 1;
			for(int k = 0; k < N; k++) {
				if(found[k]) continue;
				if(flow[k][source]) {
					ll val = dist[source] + pi[source] - pi[k] - cost[k][source];
					if(dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if(flow[source][k] < cap[source][k]) {
					ll val = dist[source] + pi[source] - pi[k] + cost[source][k];
					if(dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if(dist[k] < dist[best]) best = k;
			}
			source = best;
		}
		for(int k = 0; k < N; k++)
			pi[k] = min((ll)(pi[k] + dist[k]), INF);
		return found[sink];
	}
	pair<ll, ll> mcmf(int source, int sink) {
		ll totflow = 0, totcost = 0;
		while(search(source, sink)) {
			ll amt = INF;
			for(int x = sink; x != source; x = dad[x])
				amt = min(amt, (ll)(flow[x][dad[x]] != 0 ?
					flow[x][dad[x]] : cap[dad[x]][x] - flow[dad[x]][x]));
			for(int x = sink; x != source; x = dad[x]) {
				if(flow[x][dad[x]] != 0) {
					flow[x][dad[x]] -= amt;
					totflow -= amt * cost[x][dad[x]];
				} else {
					flow[dad[x]][x] += amt;
					totcost += amt * cost[dad[x]][x];
				}
			}
			totflow += amt;
		}
		return {totflow, totcost};
	}
};

int ts[505][505];
int ps[505];
int fl[505][3];
bool adj[505][505];
int n,m;

bool valid(int airplanes) {
	MCMF alg(2*m+5);
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < m; j++) {
			if(i == j) alg.add_edge(i,m+j,1,-1);
			else if(adj[i][j]) alg.add_edge(m+i,j,1,0);
		}
		alg.add_edge(2*m+1,i,1,0);
		alg.add_edge(m+i,2*m+2,1,0);
	}
	alg.add_edge(2*m+3,2*m+1,airplanes,0);
	return alg.mcmf(2*m+3,2*m+2).second == -m;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); cout.precision(15);

	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> ps[i];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin >> ts[i][j];
		}
	}
	for(int i = 0; i < m; i++) {
		cin >> fl[i][0] >> fl[i][1] >> fl[i][2];
	}
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < m; j++) {
			if( i == j ) continue;
			adj[i][j] = (fl[i][1] == fl[j][0]) && (fl[i][2] + ts[ fl[i][0] ][ fl[i][1] ] + ps[ fl[i][1] ] <= fl[j][2]);
		}
	}

	int low = 0, high = 505;
	while(high - low > 1) {
		int mid = (low + high) / 2;
		if( valid(mid) ) high = mid;
		else low = mid;
	}
	if(valid(low)) high = low;

	cout << high << endl;

	return 0;
}