//多源最短路;
//最小路径覆盖;
//http://acm.pku.edu.cn/JudgeOnline/problem?id=3216
#include
<stdio.h>
#include
<memory.h>
#include
<iostream>
using namespace std;

#define MAX 
21
#define M 
201
#define INFF 
-1
bool b[M];
int n,m,ans;
int g[MAX][MAX];//路径的邻接矩阵;
int link[M];
int p[MAX][MAX];
int d[MAX][MAX];
int x[M],y[M],z[M];
/*==========================================   
    http:
//topic.csdn.net/t/20020703/16/847300.html
                              多源最短路径   
                                  Floyd
-Warshall   算法   
    
          d[i,j]表示从i到j的最短距离;   
          p[i,j]表示从i到j的最短路径上j的父节点   
    
  
===========================================*/  
void Floyd_Washall(){   
          
int i,j,k;
          
for(i=1;i<=n;i++){
              
for(j=1;j<=n;j++){
                  d[i][j]
=g[i][j];
                  p[i][j]
=i;
              }
          }
          
for(i=1;i<=n;i++){
              d[i][i]
=0;
              p[i][i]
=0;
          }
          
for(k=1;k<=n;k++){
              
for(i=1;i<=n;i++){
                  
for(j=1;j<=n;j++){
                      
if(d[i][k]>=0&&d[k][j]>=0&&(d[i][j]>d[i][k]+d[k][j]||d[i][j]==INFF)){
                          d[i][j]
=d[i][k]+d[k][j];
                          p[i][j]
=p[k][j];
                      }
                  }
              }
          }
}
//最小路径覆盖;
bool find(
int a)
{
    
int j;
    
int r=x[a];
    
for(int i=1;i<=m;i++){
        j
=x[i];
        
if(d[r][j]>=0&&y[a]+z[a]+d[r][j]<=y[i]&&!b[i]){
            b[i]
=true;
            
if(link[i]==0||find(link[i])){
                link[i]
=a;
                return 
true;
            }
        }
    }
    return 
false;
}

int main()
{
    
int i,j;
    
while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
        
for(i=1;i<=n;i++){
            
for(j=1;j<=n;j++){
                scanf(
"%d",g[i]+j);
            }
        }
        
for(i=1;i<=m;i++){
            scanf(
"%d%d%d",x+i,y+i,z+i);
        }
        Floyd_Washall();
        ans
=0;
        memset(link,
0,sizeof(link));
        
for(i=1;i<=m;i++){
            memset(b,
0,sizeof(b));
            
if(find(i)){
                ans
++;
            }
        }
        printf(
"%d\n",m-ans);
    }
    return 
0;
}