//多源最短路；
//最小路径覆盖；
//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;
}