#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>

#define pb push_back

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;

const int INF = 0x3f3f3f3f;

const int N = 1e3 + 5;
int dist[N][N];
vi g[N];
int n, m, match[N];
bool vis[N];

struct node {
    ll p, t, d;
} nodes[N];

bool dfs(int u) {
    for(int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if(vis[v]) continue;
        vis[v] = true;
        if(match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

void solve() {
    for(int i = 1; i <= m; i++) {
        int p, t, d; cin >> p >> t >> d;
        nodes[i].p = p, nodes[i].t = t, nodes[i].d = d;
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= m; j++) {
            if(i == j) continue;
            if(dist[nodes[i].p][nodes[j].p] + nodes[i].t + nodes[i].d <= nodes[j].t) 
                g[i].pb(j); 
        }
    }
    int res = 0;
    memset(match, -1, sizeof(match));
    for(int i = 1; i <= m; i++) { 
        memset(vis, false, sizeof(vis));
        if(dfs(i)) res++; 
    }
    cout << m - res << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while(cin >> n >> m && n && m) {
        for(int i = 0; i <= m; i++) g[i].clear();
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                cin >> dist[i][j];
                dist[i][j] = (dist[i][j] == -1 ? INF : dist[i][j]); 
            }
        }
        
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
            	if(dist[i][k] >= INF) continue;
                for(int j = 1; j <= n; j++) {
                    if(dist[k][j] < INF)
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        solve();
    }
    return 0;
}