#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=110;
const ll maxk=1010;
const ll inf=LLONG_MAX/3;
ll n,m,k;
ll b[maxn][maxk];
ll s[maxn][maxk];
ll gt[maxn][maxn];
ll gp[maxn][maxn];
ll checkg[maxn][maxn];
void init(){
for(auto &i:gt) for(auto &j:i) j=inf;
}
void floyd(ll g[maxn][maxn]){
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
for(ll l=0;l<n;l++){
g[j][l]=min(g[j][l],g[j][i]+g[i][l]);
}
}
}
}
bool check(ll eff){
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
checkg[i][j]=inf;
if(gt[i][j]==inf) continue;
checkg[i][j]=eff*gt[i][j]-gp[i][j];
}
}
floyd(checkg);
for(ll i=0;i<n;i++){
if(checkg[i][i]<=0) return true;
}
return false;
}
int main(){
cin>>n>>m>>k;
init();
for(ll i=0;i<n;i++){
for(ll j=0;j<k;j++) cin>>b[i][j];
for(ll j=0;j<k;j++) cin>>s[i][j];
}
for(ll i=0;i<m;i++){
ll v,w,t;
cin>>v>>w>>t;
v--,w--;
gt[v][w]=min(t,gt[v][w]);
}
floyd(gt);
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
for(ll l=0;l<k;l++){
if(s[j][l]==-1 || b[i][l]==-1) continue;
gp[i][j]=max(gp[i][j],s[j][l]-b[i][l]);
}
}
}
ll l=0,r=1e9+10,res=-1;
while(l<=r){
ll mid=l+(r-l)/2;
if(check(mid)){
res=mid;
l=mid+1;
}else r=mid-1;
}
cout<<res;
return 0;
}
