/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")

//-------------------------------------------------------------//

typedef long long ll;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define all(v) v.begin(),v.end()

int main(){
    fast
    int n,m,k;cin>>n>>m>>k;
    vector<vector<ll>>a(n+1,vector<ll>(k+1));
    vector<vector<ll>>b(n+1,vector<ll>(k+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            cin>>a[i][j]>>b[i][j];
        }
    }
    vector<vector<ll>>dist(n+5,vector<ll>(n+5,1e18));
    vector<vector<bool>>vis(n+5,vector<bool>(n+5));
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        dist[u][v]=w;
        vis[u][v]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    ll l=1,r=1e18,ans=0;
    while(l<=r){
        ll mid=(l+r)>>1LL;
        vector<vector<ll>>dist2(n+5,vector<ll>(n+5,1e18));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dist[i][j]!=1e18){
                    dist2[i][j]=mid*min((ll)1e18/mid,dist[i][j]);a
                    ll mx=0;
                    for(int h=1;h<=k;h++){
                        if((~a[i][h]) && (~b[j][h])){
                            mx=max(mx,b[j][h]-a[i][h]);
                        }
                    }
                    dist2[i][j]-=mx;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    dist2[i][j]=min(dist2[j][i],dist2[i][k]+dist2[k][j]);
                }
            }
        }
        bool v=0;
        for(int i=1;i<=n;i++){
            if(dist2[i][i]<=0)v=1;
        }
        if(v){
            ans=mid;
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    if(ans==1e18)ans=0;
    cout<<ans<<endl;
}

answer.code: In function ‘int main()’:
answer.code:49:67: error: expected ‘;’ before ‘ll’
   49 |                     dist2[i][j]=mid*min((ll)1e18/mid,dist[i][j]);a
      |                                                                   ^
      |                                                                   ;
   50 |                     ll mx=0;
      |                     ~~                                             
answer.code:53:29: error: ‘mx’ was not declared in this scope; did you mean ‘m’?
   53 |                             mx=max(mx,b[j][h]-a[i][h]);
      |                             ^~
      |                             m
answer.code:56:34: error: ‘mx’ was not declared in this scope; did you mean ‘m’?
   56 |                     dist2[i][j]-=mx;
      |                                  ^~
      |                                  m