import java.io.*;
import java.util.*;
import java.awt.geom.*;

/**
 * Solution to Airports
 * 
 * @author vanb
 */
public class airports_vanb
{
    public Scanner sc;
    public PrintStream ps;
    
    /**
     * A node of a max flow graph.
     * 
     * @author vanb
     */
    public class Node
    {
        // Has the node been visited?
        public boolean visited = false;
        
        // List of edges from this node
        public LinkedList<Edge> edges = new LinkedList<Edge>();
        
        // If this node has been visited, what edge did we get here from?
        public Edge gothere = null;
    }
    
    /**
     * An edge of a max flow graph.
     * 
     * @author vanb
     */
    public class Edge
    {
        Node destination;
        int capacity;
        Edge dual;
        
        public Edge( Node d, int c )
        {
            capacity = c;
            destination = d;
            dual = null;
        }
    }
    
    /**
     * Create a link between two nodes of a max flow graph.
     * 
     * @param n1 From node
     * @param n2 To node
     * @param cost Cost to go from n1 to n2
     */
    public void link( Node n1, Node n2, int cost )
    {
        Edge e12 = new Edge( n2, cost );
        Edge e21 = new Edge( n1, 0 );
        e12.dual = e21;
        e21.dual = e12;
        n1.edges.add( e12 );
        n2.edges.add( e21 );
    }
    
    /** Queue for the Ford/Fulkerson algorithm */
    public LinkedList<Node> queue = new LinkedList<Node>();
    
    /**
     * Perform the Ford/Fulkerson algorithm on a graph.
     * 
     * @param src Source node
     * @param snk Sink node
     * @param nodes The graph, represented as a list of nodes
     * @return The max flow from the source to the sink
     */
    public int fordfulkerson( Node src, Node snk, List<Node> nodes )
    {
        int total = 0;
        
        // Keep going until you can't get from the source to the sink
        for(;;)
        {  
            // Reset the graph
            for( Node node : nodes )
            {
                node.visited = false;
                node.gothere = null;
            }

            // Reset the queue
            // Start at the source
            queue.clear();
            queue.add( src );
            src.visited = true;
            
            // Have we found the sink?
            boolean found = false;
            
            // Use a breadth-first search to find a path from the source to the sink
            while( queue.size()>0 )
            {
                Node node = queue.poll();
                
                // have we found the sink? If so, break out of the BFS.
                if( node==snk )
                {
                    found = true;
                    break;
                }
                
                // Look for edges to traverse
                for( Edge edge : node.edges )
                {
                    Node dest = edge.destination;
                    
                    // If this destination hasn't been visited,
                    // and the edge has capacity, 
                    // put it on the queue.
                    if( edge.capacity>0 && !dest.visited )
                    {
                        // Node has been visited
                        dest.visited = true;
                        
                        // Remember the edge that got us here
                        dest.gothere = edge;
                        
                        // Add to the queue
                        queue.add( dest );
                    }
                }
            }
            
            // If we were unable to get to the sink, then we're done
            if( !found ) break;
            
            // Otherwise, look along the path to find the minimum capacity
            int min = Integer.MAX_VALUE;
            for( Node node = snk; node.gothere != null; )
            {
                Edge edge = node.gothere;
                if( edge.capacity < min ) min = edge.capacity;
                node = edge.dual.destination;
            }
            
            // Add that minimum capacity to the total
            total += min;
            
            // Go back along the path, and for each edge, move the min
            // capacity from the edge to its dual.
            for( Node node = snk; node.gothere != null; )
            {
                Edge edge = node.gothere;
                edge.capacity -= min;
                edge.dual.capacity += min;
                node = edge.dual.destination;
            }        
        }
        
        // Return the total
        return total;
    }
    
    /**
     * Class to hold the info about a Flight.
     * 
     * @author vanb
     */
    public class Flight
    {
        public int s, f, t;
        
        /**
         * Create a Flight.
         * 
         * @param s Starting airport
         * @param f Destination airport
         * @param t Time of departure
         */
        public Flight( int s, int f, int t )
        {
            this.s = s;
            this.f = f;
            this.t = t;
        }
    }
        
    /**
     * Driver.
     * @throws Exception
     */
    public void doit() throws Exception
    {
        sc = new Scanner( System.in );
        ps = System.out;
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int inspections[] = new int[n];
        for( int i=0; i<n; i++ )
        {
            inspections[i] = sc.nextInt();
        }
        
        // mintimes in the minimum time it takes to get from i to j.
        // This may not be the time it takes to fly directly.
        int mintimes[][] = new int[n][n];  
        // This is the time it takes to fly directly from i to j
        int direct[][] = new int[n][n];
        for( int i=0; i<n; i++) for( int j=0; j<n; j++ )
        {
            int time = sc.nextInt();
            
            // We'll include the inspections time at the destination airport
            // in our flight times.
            mintimes[i][j] = time + inspections[j];
            direct[i][j] = time + inspections[j];
            
            // Something for the judges to verify the data....
            if( i==j && time!=0 ) System.err.println( "PANIC!! " + i + "->" + j + " !=0" );
        }
        
        // This data does NOT satisfy the triangle inequality.
        // That means, going from i to j, it may be cheaper to stop over at k
        // rather than going directly from i to j. That is, i->k->j may be shorter than i->j.
        // So, we'll use Floyd-Warshall to compute all shortest times.
        for( int k=0; k<n; k++ ) for( int i=0; i<n; i++ ) for( int j=0; j<n; j++ )
        {
            int stopover = mintimes[i][k] + mintimes[k][j];
            if( stopover < mintimes[i][j] ) mintimes[i][j] = stopover;
        }
        
        // Alright, think about this: If the airline didn't reuse any planes,
        // how many planes would they need? They'd need a different plane for each flight.
        // so obviously, the answer is m, the number of flights. 
        //
        // Suppose they could use the same plane for flight A and flight B? 
        // Then they'd only need m-1. Suppose there were 5 instances of being able
        // to reuse a plane? Then they'd need m-5.
        //
        // So, that gives us our solution strategy: Find the maximal plane reuse, and 
        // subtract that from m. 
        //
        // Finding maximal plane reuse can be seen as an optimal pairing problem:
        // Pairing flight with other flights if they can use the same plane, and then 
        // finding the maximal set of pairings.
        //
        // So, create two nodes for each flight: before, and after. Create an edge with weight
        // 1 between before[i] and after[j] iff the plane for flight i could be reused for j.
        // Create a start node with links to all of the befores with weight 1, create a sink
        // node with links all of the afters with weight 1, and just run Ford/Fulkerson on it.
        // The final answer is m - [max flow].
        List<Node> nodes = new LinkedList<Node>();
        Node source = new Node();
        Node sink = new Node();
        nodes.add( source );
        nodes.add( sink );
        
        // Create all of the nodes
        Node befores[] = new Node[m];
        Node afters[] = new Node[m];
        Flight flights[] = new Flight[m];
        for( int i=0; i<m; i++ )
        {
            int s = sc.nextInt()-1;
            int f = sc.nextInt()-1;
            int t = sc.nextInt();
            flights[i] = new Flight( s, f, t );
            
            // Create 'before' node
            befores[i] = new Node();
            nodes.add( befores[i] );
            link( source, befores[i], 1 );
            
            // Create 'after' node
            afters[i] = new Node();
            nodes.add( afters[i] );
            link( afters[i], sink, 1);
        }
        
        // Now, link'em up.
        for( int i=0; i<m; i++ ) for( int j=0; j<m; j++ ) if( i!=j )
        {
            // The time to fly flight i.
            // Note that you have to fly directly, 
            // so we have to use direct[][] instead of mintimes[][]
            int time = direct[flights[i].s][flights[i].f];
            
            // If flight i doesn't end where flight j begins,
            // then we've got to account for the time to fly the 
            // plane from i's destination airport to j's departure airport.
            // Here' we CAN use mintimes[][]!
            if( flights[i].f!=flights[j].s ) time += mintimes[flights[i].f][flights[j].s];
            
            // So.. after all that time, will it arrive at flight j's airport
            // in time for flight j's departure?
            if( flights[i].t + time <= flights[j].t )   
            {
                link( befores[i], afters[j], 1 );
            }
        }
        
        // The answer is just m - [max flow]
        ps.println( m-fordfulkerson( source, sink, nodes ) ); 
    }
    
    /**
     * @param args
     */
    public static void main( String[] args ) throws Exception
    {
        new airports_vanb().doit();        
    }   
}