#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=104,inf=5e15;
int og[N][N],tg[N][N],kg[N][N],bs[N][10*N][2],n,m,k;
bool ss(){
for(int i=0;i<n;++i)if(kg[i][i]<=0)return 1;
return 0;
}
void fw(int aa[N][N]){
for(int kk=0;kk<n;++kk){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)
aa[i][j]=min(aa[i][j],aa[i][kk]+aa[kk][j]);
}
}
}
bool chk(int x){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
int sc=min(og[i][j],inf/(1+x))*x;
kg[i][j]=sc-tg[i][j];
}
}
fw(kg);
return(ss());
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>k;
for(int i=0;i<n;++i)
fill(og[i],og[i]+n,inf);
for(int i=0;i<n;++i){
for(int j=0;j<k;++j)
cin>>bs[i][j][0]>>bs[i][j][1];
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int kk=0;kk<k;++kk)
if(bs[j][kk][1]!=-1&&bs[i][kk][0]!=-1)
tg[i][j]=max(tg[i][j],bs[j][kk][1]-bs[i][kk][0]);
}
}
for(int i=0,u,v,w;i<m;++i){
cin>>u>>v>>w;
--u,--v;
og[u][v]=w;
}
fw(og);
int l=1,r=l+1e9,ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(chk(mid)){
l=mid+1;
ans=mid;
}else
r=mid-1;
}
cout<<ans;
}
