/*
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,4e18));
    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,4e18));
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dist2[i][j]=mid*min((ll)4e18/mid,dist[i][j]);
                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[i][j],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;
        }
    }
    cout<<ans<<endl;
}