/*
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(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]+dist[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:40: error: no matching function for call to ‘min(double, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)’
   49 |                     dist2[i][j]=mid*min(1e18/mid,dist[i][j]);a
      |                                     ~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:5:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
answer.code:49:40: note:   deduced conflicting types for parameter ‘const _Tp’ (‘double’ and ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’})
   49 |                     dist2[i][j]=mid*min(1e18/mid,dist[i][j]);a
      |                                     ~~~^~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
answer.code:49:40: note:   deduced conflicting types for parameter ‘const _Tp’ (‘double’ and ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’})
   49 |                     dist2[i][j]=mid*min(1e18/mid,dist[i][j]);a
      |                                     ~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)’
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
answer.code:49:40: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘double’
   49 |                     dist2[i][j]=mid*min(1e18/mid,dist[i][j]);a
      |                                     ~~~^~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)’
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
answer.code:49:40: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘double’
   49 |                     dist2[i][j]=mid*min(1e18/mid,dist[i][j]);a
      |                                     ~~~^~~~~~~~~~~~~~~~~~~~~
answer.code:49:63: error: expected ‘;’ before ‘ll’
   49 |                     dist2[i][j]=mid*min(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