#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=107;
const ll INF=1e18+7;
ll kraw[LIM][LIM], B[LIM][10*LIM], S[LIM][10*LIM], n, k;
ll zysk[LIM][LIM], odl[LIM][LIM], tmp[LIM][LIM];
ll dist[LIM], wrz;
void poteguj() {
rep(i, 20) {
rep(i, n) rep(j, n) {
tmp[i][j]=odl[i][j];
rep(l, n) if(odl[i][l]!=-INF && odl[l][j]!=-INF) {
tmp[i][j]=max(tmp[i][j], min(INF, odl[i][l]+odl[l][j]));
}
}
rep(i, n) rep(j, n) odl[i][j]=tmp[i][j];
}
}
bool cykl(ll x) {
rep(i, n) dist[i]=-INF;
dist[x]=0;
while(true) {
ll ma=-INF, ind=-1;
rep(i, n) if(dist[i]>ma && dist[i]<INF) {
ma=dist[i];
ind=i;
}
if(ind==-1) break;
ll o=dist[ind]; dist[ind]=INF;
if(o+odl[ind][x]>=0) return true;
rep(i, n) {
if(dist[i]<INF && dist[i]<o+odl[ind][i]) {
dist[i]=o+odl[ind][i];
dist[i]=min(dist[i], INF-1);
}
}
}
return false;
}
bool f(ll x) {
rep(i, n) rep(j, n) {
if(kraw[i][j]==-INF) odl[i][j]=-INF;
else {
odl[i][j]=kraw[i][j]*x;
if(zysk[i][j]>=0) odl[i][j]+=zysk[i][j];
}
}
rep(i, n) rep(j, n) odl[i][j]*=-1;
rep(k, n) rep(i, n) rep(j, n) if(odl[i][k]<INF && odl[k][j]<INF) {
odl[i][j]=min(odl[i][j], odl[i][k]+odl[k][j]);
}
rep(i, n) if(odl[i][i]<=0) return true;
return false;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int m;
cin >> n >> m >> k;
rep(i, n) rep(j, n) kraw[i][j]=-1;
rep(i, n) rep(j, k) cin >> B[i][j] >> S[i][j];
rep(i, m) {
ll a, b, c;
cin >> a >> b >> c; --a; --b;
if(kraw[a][b]==-1) kraw[a][b]=c;
kraw[a][b]=min(kraw[a][b], c);
}
rep(i, n) rep(j, n) {
zysk[i][j]=-INF;
rep(l, k) if(i!=j && B[i][l]!=-1 && S[j][l]!=-1) {
zysk[i][j]=max(zysk[i][j], S[j][l]-B[i][l]);
}
}
rep(i, n) rep(j, n) if(kraw[i][j]==-1) odl[i][j]=-INF; else odl[i][j]=-kraw[i][j];
poteguj();
rep(i, n) rep(j, n) kraw[i][j]=odl[i][j];
ll po=0, ko=1000000000;
while(po<ko) {
ll sr=(po+ko+1)/2;
if(f(sr)) po=sr; else ko=sr-1;
}
cout << po << '\n';
}
