#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 4000000000000000000ll
#define M 10000002
#define N 105
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;
int n,m,k,x,y,z;
int b[N][N*10],s[N][N*10];
ll p[N][N],d1[N][N],d2[N][N];
bool neg(int pro) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(d1[i][j]==inf) d2[i][j]=inf;
else d2[i][j]=1ll*d1[i][j]*pro-p[i][j];
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++) {
umin(d2[j][k],d2[j][i]+d2[i][k]);
}
}
}
for(int i=1;i<=n;i++) {
if(d2[i][i]<=0) return true;
}
return false;
}
int main() {
#if 0
freopen("input.txt","r",stdin);
#endif
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++) {
for(int j=1;j<=k;j++) {
scanf("%d %d",&b[i][j],&s[i][j]);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
d1[i][j]=inf;
}
}
for(int i=1;i<=m;i++) {
scanf("%d %d %d",&x,&y,&z);
umin(d1[x][y],1ll*z);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++) {
umin(d1[j][k],d1[j][i]+d1[i][k]);
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int g=1;g<=k;g++) {
if(~s[j][g] && ~b[i][g]) {
umax(p[i][j],1ll*s[j][g]-b[i][g]);
}
}
}
}
/*for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%d ",p[i][j]);
printf("\n\n\n\n");
for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%lld ",d1[i][j]);*/
int bas=1,son=1e9;
while(bas<=son) {
if(neg(orta)) bas=orta+1;
else son=orta-1;
}
printf("%d",son);
//printf("%lld",LONG_LONG_MAX);
}
