#include<bits/stdc++.h>
#define int long long
using namespace std;
int b[105][1005];
int s[105][1005];
int dis[105][105];
int dis2[105][105];
int inf=1e15;
int n,m,k;
int can(int md){
//cerr<<"md:"<<md<<"\n";
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis2[i][j]=-inf;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
if(dis[i][j]!=inf){
dis2[i][j]=-md*dis[i][j];
for(int l=1;l<=k;l++){
if(s[j][l]==-1||b[i][l]==-1)continue;
dis2[i][j]=max(dis2[i][j],s[j][l]-b[i][l]-md*dis[i][j]);
}
}
}
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++){
dis2[j][k]=max(dis2[j][k],dis2[j][i]+dis2[i][k]);
}
for(int i=1;i<=n;i++)if(dis2[i][i]>=0)return 1;
return 0;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
cin>>b[i][j]>>s[i][j];
}
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=inf;
for(int i=1;i<=n;i++)dis[i][i]=0;
for(int i=1;i<=m;i++){
int a,b,c;cin>>a>>b>>c;
dis[a][b]=c;
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++){
dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
}
int st=0,en=1e9,ans=0;
while(st<=en){
int m=(st+en)/2;
if(can(m)){
st=m+1;
ans=m;
}else{
en=m-1;
}
}
cout<<ans<<"\n";
}
