> #include<iostream>
> #include<cstring>
> using namespace std;
> bool mapp[202][202];
> int dis[30][30];
> int q,m;
> struct node{
> 	int p,t,d;
> }tasks[202];
> void ini(){
> 	memset(mapp,0,sizeof(mapp));
> 	memset(dis,0,sizeof(dis));
> }
> int qq[202];
> int vm1[202];
> int vm2[202];
> int pre[202];
> int hungary(bool mapp[][202],int v1,int v2){
> 	int n = 0;
> 	int current;
> 	memset(vm1,-1,sizeof(vm1));
> 	memset(vm2,-1,sizeof(vm2));
> 
> 	int head,tail;
> 	int i,j,k;
> 	for(i =0;i<v1;i++){
> 		head = tail = 0;
> 		memset(pre,-2,sizeof(pre));
> 		for(j = 0;j<v2;j++){
> 			if(mapp[i][j]){
> 				qq[tail++] = j;
> 				pre[j]=  -1;
> 			}
> 		}
> 		while(head<tail){
> 			current = qq[head];
> 			if(vm2[current] == -1)break;
> 			head++;
> 			for(j = 0;j<v2;j++){
> 				if(pre[j] == 0xfefefefe && mapp[vm2[current]][j]){
> 					pre[j] = current;
> 					qq[tail++] = j;
> 				}
> 			}
> 		}
> 		if(head == tail)continue;
> 		while(pre[current] != -1){
> 			vm1[vm2[pre[current]]] = current;
> 			vm2[current] = vm2[pre[current]];
> 			current = pre[current];
> 		}
> 		vm1[i] = current;
> 		vm2[current] = i;
> 		n++;
> 	}
> 	return n;
> }
> 
> 
> void solve(){
> 	int i,j,k;
> 	for(i = 0;i<q;i++){
> 		for(j = 0;j<q;j++){
> 			cin>>dis[i][j];
> 			if(dis[i][j] = -1)dis[i][j] = 100000000;
> 		}
> 	}
> 	//floyd for shortest path
> 	for(i = 0;i<q;i++){
> 		for(j = 0;j<q;j++){
> 			if(dis[j][i] != 100000000){
> 				for(k= 0 ;k<q;k++){
> 					if(dis[j][k] > dis[j][i] + dis[i][k] )
> 						dis[j][k] = dis[j][i] + dis[i][k];
> 				}
> 			}
> 		}
> 	}
> 	int p,t,d;
> 	for(i = 0;i<m;i++){
> 		cin>>p>>tasks[i].t>>tasks[i].d;
> 		tasks[i].p = p - 1;
> 	}
> 	//build the graph
> 	for(i = 0;i<m;i++){
> 		for(j = 0;j<m;j++){
> 			//if repair man can finish and show up on time 
> 			if(tasks[i].t + tasks[i].d + dis[tasks[i].p][tasks[j].p] <= tasks[j].t)
> 				mapp[i][j] = true;
> 			else 
> 				mapp[i][j] = false;
> 		}
> 	}
> 	// hungary is a version of b_graph matching
> 	cout<<m - hungary(mapp,m,m)<<endl;
> }
> 
> int main(){
> 	//freopen("in.txt","r",stdin);
> 	cin>>q>>m;
> 	while(q!=0 && m != 0){
> 		ini();
> 		solve();
> 		cin>>q>>m;
> 	}
> 	return 0;
> }
> 
up