#include<bits/stdc++.h>
using namespace std;
const long long INF=1e18;
long long dp[105][105],S[105][1005],B[105][1005],F[105][105],P[105][105];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=1e9*(i!=j);
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<=m;i++)
{
int l,r,v;
cin>>l>>r>>v;
dp[l][r]=min(dp[l][r],(long long)v);
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{
F[i][j]=0;
for(int l=1;l<=k;l++) if(B[i][l]!=-1&&S[j][l]!=-1) F[i][j]=max(F[i][j],S[j][l]-B[i][l]);
}
int l=0,r=1e9,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
bool ck=false;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) P[i][j]=dp[i][j]*mid-F[i][j];
for(int i=1;i<=n;i++) P[i][i]=INF;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) P[j][k]=min(P[j][k],max(-INF,P[j][i]+P[i][k]));
for(int i=1;i<=n;i++) ck|=(P[i][i]<=0);
if(ck) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans;
}
