// Arup Guha
// 11/17/2015
// Solution to 2015 SER D1 Problem: Airports

// Note: This is the second solution that I wrote, after talking to Evan
//       and Eric. My first one is definitely much slower than this one and this
//       is what was intended (running flow once without any costs...)

import java.util.*;
import java.io.*;

public class airports {

	final public static int NOPATH = 1000000000;

	// Lots of stuff to store for this problem...
	public static int numLocs;
	public static int numFlights;
	public static int[] inspectTime;
	public static int[][] adj;
	public static flight[] flights;
	public static int[][] floyd;

	public static void main(String[] args) throws Exception {

		// Read in size info.
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		numLocs = Integer.parseInt(tok.nextToken());
		numFlights = Integer.parseInt(tok.nextToken());

		// Read in inspection times.
		tok = new StringTokenizer(stdin.readLine());
		inspectTime = new int[numLocs];
		for (int i=0; i<numLocs; i++)
			inspectTime[i] = Integer.parseInt(tok.nextToken());

		// Read in adjacency matrix.
		adj = new int[numLocs][numLocs];
		for (int i=0; i<numLocs; i++) {
			tok = new StringTokenizer(stdin.readLine());
			for (int j=0; j<numLocs; j++)
				adj[i][j] = Integer.parseInt(tok.nextToken());
		}

		// Read in flights.
		flights = new flight[numFlights];
		for (int i=0; i<numFlights; i++) {
			tok = new StringTokenizer(stdin.readLine());
			int start = Integer.parseInt(tok.nextToken()) - 1;
			int end = Integer.parseInt(tok.nextToken()) - 1;
			int go = Integer.parseInt(tok.nextToken());
			flights[i] = new flight(start, end, go, go+adj[start][end]+inspectTime[end]);
		}

		// Fill in our effective travel times (for additional flights)
		calcFloyd();

		// Create our generic flow graph, with # of planes NOT filled in.
		netflow myFlow = createFlowGraph();

		// The result is numFlights minus the max Flow (maximal anti-chain).
		System.out.println(numFlights - myFlow.getMaxFlow());
	}

	public static void calcFloyd() {

		// Need a slightly different adjacency matrix for our purposes.
		floyd = new int[numLocs][numLocs];
		for (int i=0; i<numLocs; i++)
			for (int j=0; j<numLocs; j++)
				floyd[i][j] = i == j ? 0 : adj[i][j] + inspectTime[j];

		// Usual Floyd-Warshall Algorithm.
		for (int k=0; k<numLocs; k++)
			for (int i=0; i<numLocs; i++)
				for (int j=0; j<numLocs; j++)
					floyd[i][j] = Math.min(floyd[i][j], floyd[i][k]+floyd[k][j]);
	}

	public static netflow createFlowGraph() {

		// Allocate space.
		int n = 2*numFlights + 2;
		int[][] capacity = new int[n][n];

        // Source and sink connections.
        for (int i=1; i<=numFlights; i++) {
            capacity[0][i] = 1;
            capacity[numFlights+i][n-1] = 1;
        }

		// These are the critical connections, we connect node i to node j iff the same plane can conduct
		// flight i and then conduct flight j. In the flow graph we add an edge from ending flight i to
		// beginning flight j.
		for (int i=0; i<numFlights; i++) {
			for (int j=0; j<numFlights; j++) {

				// This is non-sensical.
				if (i == j) continue;

				// Calculate when a plane completing flight i would be ready to fly flight j.
				int ready = flights[i].ready + floyd[flights[i].end][flights[j].start];
				if (ready <= flights[j].depart)
					capacity[i+1][numFlights+j+1] = 1;
			}
		}

		return new netflow(capacity, 0, n-1);
	}
}

class flight {

	public int start;
	public int end;
	public int depart;
	public int ready;

	public flight(int s, int e, int t, int r) {
		start = s;
		end = e;
		depart = t;
		ready = r;
	}
}

/*** My network flow code ***/
class Edge {

	public int dest;
	private int capacity;
	private int flow;

	public Edge(int cap, int d) {
		capacity = cap;
		flow = 0;
		dest = d;
	}

	public int maxPushForward() {
		return capacity - flow;
	}

	public int maxPushBackward() {
		return flow;
	}

	public boolean pushForward(int moreflow) {

		// We can't push through this much flow.
		if (flow+moreflow > capacity)
			return false;

		// Push through.
		flow += moreflow;
		return true;
	}

	public boolean pushBack(int lessflow) {

		// Not enough to push back on.
		if (flow < lessflow)
			return false;

		flow -= lessflow;
		return true;
	}
}

class direction {

	public int prev;
	public boolean forward;

	public direction(int node, boolean dir) {
		prev = node;
		forward = dir;
	}

	public String toString() {
		if (forward)
			return "" + prev + "->";
		else
			return "" + prev + "<-";
	}
}

class netflow {

	private Edge[][] adjMat;
	private int source;
	private int dest;
	private HashMap[] lookup;
	private LinkedList[] backEdgeLookup;

	// All positive entries in flows should represent valid flows
	// between vertices. All other entries must be 0 or negative.
	public netflow(int[][] flows, int start, int end) {

		source = start;
		dest = end;
		adjMat = new Edge[flows.length][];
		lookup = new HashMap[flows.length];

		backEdgeLookup = new LinkedList[flows.length];
		for (int i=0; i<flows.length; i++)
			backEdgeLookup[i] = new LinkedList<Integer>();

		for (int i=0; i<flows.length; i++) {

			lookup[i] = new HashMap<Integer,Integer>();

			int numEdges = 0;
			for (int j=0; j<flows[i].length; j++)
				if (flows[i][j] > 0)
					numEdges++;

			adjMat[i] = new Edge[numEdges];

			int cnt = 0;
			for (int j=0; j<flows[i].length; j++) {

				// Fill in this flow.
				if (flows[i][j] > 0) {
					lookup[i].put(j, cnt);
					adjMat[i][cnt++] = new Edge(flows[i][j], j);
					backEdgeLookup[j].offer(i);
				}
			}
		}
	}

	public ArrayList<direction> findAugmentingPath() {

		// This will store the previous node visited in the BFS.
		direction[] prev = new direction[adjMat.length];
		boolean[] inQueue = new boolean[adjMat.length];
		for (int i=0; i<inQueue.length; i++)
			inQueue[i] = false;

		// The source has no previous node.
		prev[source] = new direction(-1, true);

		LinkedList<Integer> bfs_queue = new LinkedList<Integer>();
		bfs_queue.offer(new Integer(source));
		inQueue[source] = true;

		// Our BFS will go until we clear out the queue.
		while (bfs_queue.size() > 0) {

			// Add all the new neighbors of the current node.
			Integer next = bfs_queue.poll();


			// Find all neighbors and add into the queue. These are forward edges.
			for (int i=0; i<adjMat[next].length; i++) {

				int item = adjMat[next][i].dest;
				if (!inQueue[item] && adjMat[next][i].maxPushForward() > 0) {
					bfs_queue.offer(item);
					inQueue[item] = true;
					prev[item] = new direction(next, true);
				}
			}

			/*** We really want i to next. ***/
			// Now look for back edges.
			for (int i=0; i<backEdgeLookup[next].size(); i++) {

				int item = (Integer)backEdgeLookup[next].pollFirst();
				if (!inQueue[item] && lookup[item].containsKey(next) && adjMat[item][(Integer)(lookup[item].get(next))].maxPushBackward() > 0) {
					bfs_queue.offer(item);
					inQueue[item] = true;
					prev[item] = new direction(next, false);
				}
				backEdgeLookup[next].offer(item);
			}
		}

		// No augmenting path found.
		if (!inQueue[dest])
			return null;

		ArrayList<direction> path = new ArrayList<direction>();

		direction place = prev[dest];

		direction dummy = new direction(dest, true);
		path.add(dummy);

		// Build the path backwards.
		while (place.prev != -1) {
			path.add(place);
			place = prev[place.prev];
		}

		// Reverse it now.
		Collections.reverse(path);

		return path;
	}

	// Run the Max Flow Algorithm here.
	public int getMaxFlow() {

		int flow = 0;

		ArrayList<direction> nextpath = findAugmentingPath();

		// Loop until there are no more augmenting paths.
		while (nextpath != null) {

			// Check what the best flow through this path is.
			int this_flow = Integer.MAX_VALUE;
			for (int i=0; i<nextpath.size()-1; i++) {

				if (nextpath.get(i).forward) {
					this_flow = Math.min(this_flow, adjMat[nextpath.get(i).prev][(Integer)lookup[nextpath.get(i).prev].get(nextpath.get(i+1).prev)].maxPushForward());
				}
				else {
					this_flow = Math.min(this_flow, adjMat[nextpath.get(i+1).prev][(Integer)lookup[nextpath.get(i+1).prev].get(nextpath.get(i).prev)].maxPushBackward());
				}
			}

			// Now, put this flow through.
			for (int i=0; i<nextpath.size()-1; i++) {

				if (nextpath.get(i).forward) {
					adjMat[nextpath.get(i).prev][(Integer)lookup[nextpath.get(i).prev].get(nextpath.get(i+1).prev)].pushForward(this_flow);
				}
				else {
					adjMat[nextpath.get(i+1).prev][(Integer)lookup[nextpath.get(i+1).prev].get(nextpath.get(i).prev)].pushBack(this_flow);
				}
			}

			// Add this flow in and then get the next path.
			flow += this_flow;
			nextpath = findAugmentingPath();
		}

		return flow;
	}

}