#include<stdio.h>
#include<string.h>
#include<limits.h>
#define MAX 201
int f[21][21];
bool dis[201][201];
struct Node
{
 int p,t,d;
}node[201];
int Q,M;
int Bipartite(bool vc[][MAX],int nv1,int nv2) { 
   int i, j, x, n; 
   int q[MAX], prev[MAX], qs, qe; 
   int vm1[MAX], vm2[MAX]; 

   n = 0; 
   for( i = 0; i < nv1; i++ ) vm1[i] = -1; 
   for( i = 0; i < nv2; i++ ) vm2[i] = -1; 
   for( i = 0; i < nv1; i++ ) { 
       for( j = 0; j < nv2; j++ ) prev[j] = -2; 
       qs = qe = 0; 
       for( j = 0; j < nv2; j++ ) if( vc[i][j] ) { 
           prev[j] = -1; 
           q[qe++] = j; 
       } 
       while( qs < qe ) { 
           x = q[qs]; 
           if( vm2[x] == -1 ) break; 
           qs++; 
           for( j = 0; j < nv2; j++ ) if( prev[j] == -2 && vc[vm2[x]][j] ) { 
               prev[j] = x; 
               q[qe++] = j; 
           } 
       } 
       if( qs == qe ) continue; 
       while( prev[x] > -1 ) { 
           vm1[vm2[prev[x]]] = x; 
           vm2[x] = vm2[prev[x]]; 
           x = prev[x]; 
       } 
       vm2[x] = i; 
       vm1[i] = x; 
       n++; 
   } 
   return n; 
} 
void floyed()
{
 int i,j,k;
 for(k=0;k<M;k++)
 {
 for(i=0;i<M;i++)
 {
  if(f[i][k]!=INT_MAX)
  {
 for(j=0;j<M;j++)
 if(f[i][k]+f[k][j]<f[i][j])
 f[i][j]=f[i][k]+f[k][j]; 
}
 }  
} 

}
int main()
{
 int i,j,k,ans;
 
 while(1)
 {
 scanf("%d%d",&Q,&M);
 if(Q+M==0)break;
 //memset(f,0,sizeof(f));
 
 for(i=0;i<Q;i++)
 for(j=0;j<Q;j++)
 {
 scanf("%d",&f[i][j]);
 if(f[i][j]==-1)f[i][j]=INT_MAX;
 }
 floyed();
 for(i=0;i<M;i++)
 {scanf("%d%d%d",&node[i].p,&node[i].t,&node[i].d);node[i].p--;}
 for(i=0;i<M;i++)
 {
  for(j=0;j<M;j++)
  {
  if(node[i].t+node[i].d+f[node[i].p][node[j].p]<=node[j].t)
  dis[i][j]=1;
  else dis[i][j]=0;
  }
 }
 ans=M-Bipartite(dis,M,M);
 printf("%d\n",ans);
 }
}