#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll oo=1e9;
const ll maxans=1e9;
ll n,m,k,buys[109][1009],sell[109][1009],cost[109][109],dist[109][109],f[109][109],u,v,w,ans,i,j,l;
bool ok(ll x) {
for (ll ii=1;ii<=n;ii++) {
for (ll ij=1;ij<=n;ij++) {
f[ii][ij]=cost[ii][ij]-dist[ii][ij]*x;
}
}
for (ll ii=1;ii<=n;ii++) {
for (ll ij=1;ij<=n;ij++) {
for (ll jj=1;jj<=n;jj++) {
f[ij][jj]=max(f[ij][jj],f[ij][ii]+f[ii][jj]);
}
}
}
for (ll ii=1;ii<=n;ii++) {
if (f[ii][ii]>=0) {
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
for (i=1;i<=n;i++) {
for (j=1;j<=k;j++) {
cin>>buys[i][j];
cin>>sell[i][j];
}
}
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
dist[i][j]=oo;
}
}
for (i=1;i<=m;i++) {
cin>>u>>v>>w;
dist[u][v]=w;
}
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
for (l=1;l<=n;l++) {
dist[j][l]=min(dist[j][l],dist[j][i]+dist[i][l]);
}
}
}
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
for (l=1;l<=k;l++) {
if (buys[i][l]!=-1) {
if (sell[j][l]!=-1) {
cost[i][j]=max(cost[i][j],sell[j][l]-buys[i][l]);
}
}
}
}
}
/*
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
cout<<dist[i][j]<<' ';
}
cout<<'\n';
}
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
cout<<cost[i][j]<<' ';
}
cout<<'\n';
}
*/
ans=0;
for (i=maxans;i>0;i/=2) {
while (ok(ans+i)) {
ans+=i;
}
}
cout<<ans<<'\n';
}
