#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,ll,ll> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
int n,m,k;
ll X[100][1000],Y[100][1000],dist[100][100],p[100][100],a[100][100];
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
cin>>n>>m>>k;
REP(i,0,n)REP(j,0,k)cin>>X[i][j]>>Y[i][j];
REP(i,0,100)REP(j,0,100)dist[i][j]=INF;
REP(i,0,m){
int x,y;cin>>x>>y;
ll z;cin>>z;
x--;y--;
dist[x][y]=z;
}
REP(i,0,n)dist[i][i]=0;
REP(x,0,n)REP(i,0,n)REP(j,0,n)if(dist[i][x]!=INF&&dist[x][j]!=INF)dist[i][j]=min(dist[i][j],dist[i][x]+dist[x][j]);
REP(i,0,n)REP(j,0,n){
if(i==j)continue;
p[i][j]=0;
if(dist[i][j]!=INF)REP(x,0,k)if(Y[j][x]!=-1&&X[i][x]!=-1)p[i][j]=max(p[i][j],Y[j][x]-X[i][x]);
}
ll l=0,r=1e18;
while(l!=r){
ll m=(l+r)/2+1;
bool flag=0;
REP(i,0,n)REP(j,0,n){
if(i==j)a[i][j]=INF;
else if(dist[i][j]==INF)a[i][j]=INF;
else a[i][j]=dist[i][j]*m-p[i][j];
}
REP(x,0,n)REP(i,0,n)REP(j,0,n)if(a[i][x]!=INF&&a[x][j]!=INF)a[i][j]=min(a[i][j],a[i][x]+a[x][j]);
REP(i,0,n)if(a[i][i]<=0)flag=1;
if(flag)l=m;
else r=m-1;
}
cout<<l;
}
