#include<bits/stdc++.h>
using namespace std;
#define db(val) "["#val" = "<<(val)<<"] "
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define FOD(i,l,r) for(int i=(l);i>=(r);i--)
#define REP(i,l,r) for(int i=(l);i<(r);i++)
using ll=long long;
template<class T> void MAX(T &x,T y){if(x<y)x=y;}
template<class T> void MIN(T &x,T y){if(x>y)x=y;}
const ll inf=1e18;
const int N=105,K=1005;
ll xet[N][N],d[N][N],c[N][N];
ll b[N][K],s[N][K];
int n,m,k;
bool ok(ll f){
FOR(i,1,n)FOR(j,1,n)
xet[i][j]=1ll*f*min(inf/f,d[i][j])-c[i][j];
FOR(k,1,n)FOR(i,1,n)FOR(j,1,n)
MIN(xet[i][j],xet[i][k]+xet[k][j]);
FOR(i,1,n)if(xet[i][i]<=0)return 1;
return 0;
}
void solve(){
cin>>n>>m>>k;
FOR(i,1,n)FOR(j,1,k)
cin>>b[i][j]>>s[i][j];
FOR(i,1,n)FOR(j,1,n)d[i][j]=inf;
FOR(i,1,m){
int x,y,t;cin>>x>>y>>t;
d[x][y]=t;
}
FOR(k,1,n)FOR(i,1,n)FOR(j,1,n)
MIN(d[i][j],d[i][k]+d[k][j]);
FOR(k,1,n)FOR(i,1,n)FOR(j,1,n)
if(s[j][k]!=-1&&b[i][k]!=-1)
MAX(c[i][j],s[j][k]-b[i][k]);
ll l=1,r=1e9,ans=0;
while(l<=r){
ll mid=(l+r)/2;
if(ok(mid)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
// assert(ans!=-1);
cout<<ans;
}
int32_t main(){
cin.tie(0)->ios::sync_with_stdio(0);
if(fopen("input.txt","r")){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen(".log","w",stderr);
}
int tt=1;
// cin>>tt;
while(tt--){
solve();
cout<<'\n';
}
return 0;
}
