#include<bits/stdc++.h>
using namespace std;
// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;
signed main(){
int N,M,K;cin>>N>>M>>K;
vector<vector<int>> B(N,vector<int>(K)),S(N,vector<int>(K));
rep(i,N){
rep(j,K){
cin>>B[i][j];
cin>>S[i][j];
}
}
vector<vector<int>> d(N,vector<int>(N,1e18));
rep(i,N)d[i][i]=0;
rep(i,M){
int v,w,t;cin>>v>>w>>t;v--;w--;
d[v][w]=min(d[v][w],t);
}
rep(k,N)rep(i,N)rep(j,N){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
vector<vector<int>> mxd(N,vector<int>(N,0));
rep(i,N)rep(j,N){
rep(k,K){
if(B[i][k]!=-1&&S[j][k]!=-1)mxd[i][j]=max(mxd[i][j],S[j][k]-B[i][k]);
}
}
// int ans=0;
// rng(i,1,N){
// if(d[0][i]==1e18)continue;
// // cout<<i<<" : "<<mxd[0][i]<<" "<<d[0][i]<<endl;
// ans=max(ans,mxd[0][i]/(d[0][i]+d[i][0]));
// }
// cout<<ans<<endl;
// return 0;
// rep(i,N){
// cout<<i<<" : ";
// rep(j,N)cout<<mxd[i][j]<<" ";
// cout<<endl;
// }
auto judge=[&](int val)->bool {
vector<vector<int>> dif(N,vector<int>(N));
rep(i,N)rep(j,N){
if(i==j)dif[i][j]=1e18;
else{
if(d[i][j]==1e18)dif[i][j]=1e18;
else dif[i][j]=val*d[i][j]-mxd[i][j];
}
}
rep(k,N)rep(i,N)rep(j,N){
dif[i][j]=min(dif[i][j],dif[i][k]+dif[k][j]);
}
rep(i,N){
if(dif[i][i]<=0){
return 1;
}
}
return 0;
};
int ok=0,ng=1e9+1;
while(abs(ok-ng)>1){
int mid=(ok+ng)>>1;
if(judge(mid))ok=mid;
else ng=mid;
}
cout<<ok<<endl;
}
