//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pairta'fang'
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn=111;
int N,M,K;
int S[maxn][maxn*maxn],B[maxn][maxn*maxn];
int dis[maxn][maxn];
int dp[maxn][maxn];
ll d[maxn][maxn],mp[maxn][maxn];
bool check(int val) {
rep(i,0,N)
rep(j,0,N) {
if (i==j) mp[i][j]=d[i][j]=0;
else if (dis[i][j]<mod) mp[i][j]=d[i][j]=1ll*dis[i][j]*val-dp[i][j];
else mp[i][j]=d[i][j]=1e12;
}
ll len=1;
rep(k,0,N) {
rep(i,0,k)
rep(j,0,k) len=min(len,d[i][j]+mp[j][k]+mp[k][i]);
rep(i,0,N)
rep(j,0,N) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
return len<=0;
}
int main() {
// freopen("input.txt","r",stdin);
std::ios::sync_with_stdio(false);cin.tie();
cin>>N>>M>>K;
memset(dis,0x3f,sizeof(dis));
rep(i,0,N) {
rep(j,0,K) cin>>B[i][j]>>S[i][j];
}
rep(i,0,M) {
int u,v,w;
cin>>u>>v>>w;
u--,v--;
dis[u][v]=min(dis[u][v],w);
}
rep(k,0,N)
rep(i,0,N)
rep(j,0,N) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
rep(i,0,N)
rep(j,0,N) {
dp[i][j]=0;
rep(k,0,K) {
if (B[i][k]==-1||S[j][k]==-1) continue;
dp[i][j]=max(dp[i][j],-B[i][k]+S[j][k]);
// cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j]<<endl;
}
}
int l=0,r=1e9;
while (l<r) {
int mid=l+r+1>>1;
if (check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}
