#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int maxn=;

const int oo=;

int n,m;

int w[maxn];

int d[maxn][maxn];//d[x][y]从x到y，w[x]w[y]不算的最短路

int g[maxn][maxn];

int rs[maxn],rt[maxn],rb[maxn];

struct Edge{

    int from,to,cap,flow;

};

vector<int>G[maxn];

vector<Edge>edges;

void Addedge(int x,int y,int z){

    Edge e;

    e.from=x;e.to=y;e.cap=z;e.flow=;

    edges.push_back(e);

    e.from=y;e.to=x;e.cap=;e.flow=;

    edges.push_back(e);

    int c=edges.size();

    G[x].push_back(c-);

    G[y].push_back(c-);

}

int s,t;

int vis[maxn];

int dd[maxn];

queue<int>q;

int Bfs(){

    memset(vis,,sizeof(vis));

    vis[s]=;dd[s]=;q.push(s);

    while(!q.empty()){

        int x=q.front();q.pop();

        for(int i=;i<G[x].size();++i){

            Edge e=edges[G[x][i]];

            if((e.cap>e.flow)&&(!vis[e.to])){

                vis[e.to]=;

                dd[e.to]=dd[x]+;

                q.push(e.to);

            }

        }

    }

    return vis[t];

}

int cur[maxn];

int Dfs(int x,int a){

    if((x==t)||(a==))return a;

    int nowflow=,f=;

    for(int i=cur[x];i<G[x].size();++i){

        cur[x]=i;

        Edge e=edges[G[x][i]];

        if((dd[x]+==dd[e.to])&&((f=Dfs(e.to,min(a,e.cap-e.flow)))>)){

            nowflow+=f;

            a-=f;

            edges[G[x][i]].flow+=f;

            edges[G[x][i]^].flow-=f;

            if(a==)break;

        }

    }

    return nowflow;

}

int Maxflow(){

    int flow=;

    while(Bfs()){

        memset(cur,,sizeof(cur));

        flow+=Dfs(s,oo);

    }

    return flow;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;++i)scanf("%d",&w[i]);

    for(int i=;i<=n;++i){

        for(int j=;j<=n;++j){

            scanf("%d",&d[i][j]);

            g[i][j]=d[i][j];

        }

    }

    for(int k=;k<=n;++k){

        for(int i=;i<=n;++i){

            for(int j=;j<=n;++j){

                if(d[i][k]+w[k]+d[k][j]<d[i][j]){

                    d[i][j]=d[i][k]+w[k]+d[k][j];

                }

            }

        }

    }

    for(int i=;i<=m;++i){

        scanf("%d%d%d",&rs[i],&rt[i],&rb[i]);

    }

    s=m+m+;t=s+;

    for(int i=;i<=m;++i)Addedge(s,i,);

    for(int i=;i<=m;++i)Addedge(i+m,t,);

    for(int i=;i<=m;++i){

        for(int j=;j<=m;++j){

            if(i==j)continue;

//            cout<<i<<' '<<j<<' '<<w[rs[j]]<<' '<<d[rt[i]][rs[j]]+w[rs[j]]<<endl;

            if(rb[i]+g[rs[i]][rt[i]]+w[rt[i]]+((rt[i]!=rs[j])?d[rt[i]][rs[j]]+w[rs[j]]:)<=rb[j]){

                Addedge(i,m+j,);

            }

        }

    }

    cout<<m-Maxflow()<<endl;

    return ;

}