#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
using pii=pair<int,int>;
using pli=pair<long long,int>;
const long long inf=1e18;
long long d[109][109];
long long b[109][1009];
long long s[109][1009];
bool ck[109][109];
long long f[109][109];
int n,m,k;
bool check(long long mid){
for1(i,1,n){
for1(j,1,n){
f[i][j]=-inf;
}
}
for1(i,1,n){
for1(j,1,n){
if (ck[i][j]||i==j)continue;
long long cost=0;
for1(l,1,k){
if (b[i][l]==-1||s[j][l]==-1)continue;
cost=max(cost,s[j][l]-b[i][l]);
}
cost=cost-d[i][j]*mid;
f[i][j]=max(f[i][j],cost);
}
}
for1(l,1,n){
for1(i,1,n){
for1(j,1,n){
f[i][j]=max(f[i][j],f[i][l]+f[l][j]);
}
}
}
for1(i,1,n){
if (f[i][i]>=0)return true;
}
return false;
}
signed main(){
srand(time(0));
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(".INP","r",stdin);
//freopen(".OUT","w",stdout);
cin>>n>>m>>k;
for1(i,1,n){
for1(j,1,n){
d[i][j]=inf;
}
d[i][i]=0;
}
for1(i,1,n){
for1(j,1,k){
cin>>b[i][j]>>s[i][j];
}
}
for1(i,1,m){
int u,v;
long long w;
cin>>u>>v>>w;
d[u][v]=min(d[u][v],w);
}
for1(z,1,n){
for1(x,1,n){
for1(y,1,n){
d[x][y]=min(d[x][y],d[x][z]+d[z][y]);
}
}
}
for1(i,1,n){
for1(j,1,n){
ck[i][j]=(d[i][j]==inf);
}
}
long long l1=1,r1=1e10,ans=0;
while (l1<=r1){
long long mid=(l1+r1)/2;
if (check(mid)){
l1=mid+1;
ans=mid;
}
else r1=mid-1;
}
cout<<ans;
}
