#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll n,m,k,i,j,q,z;
cin>>n>>m>>k;
ll val=1e18;
vector<vector<ll>> b(n+1,vector<ll>(k+1));
vector<vector<ll>> s(n+1,vector<ll>(k+1));
vector<vector<ll>> e(n+1,vector<ll>(n+1,1e18));
vector<vector<ll>> graph(n+1,vector<ll>(n+1,1e18));
vector<vector<ll>> e1(n+1,vector<ll>(n+1));
vector<vector<ll>> profit(n+1,vector<ll>(n+1,0));
for(i=1 ; i<=n ; i++){
for(j=1 ; j<=k ; j++){
cin>>b[i][j]>>s[i][j];
}
}
for(i=1 ; i<=m ; i++){
cin>>j>>q>>z;
e[j][q]=z;
}
for(i=1 ; i<=n ; i++){
for(j=1 ; j<=n ; j++){
for(q=1 ; q<=n ; q++){
e[j][q]=min(e[j][q],e[j][i]+e[i][q]);
}
}
}
for(i=1 ; i<=n ; i++){
for(j=1 ; j<=n ; j++){
for(q=1 ; q<=k ; q++){
if(s[j][q]==-1 or b[i][q]==-1) continue;
profit[i][j]=max(profit[i][j],s[j][q]-b[i][q]);
}
}
}
ll ok=0,ng=1e9+1;
while(ng-ok>1){
ll mid=(ng+ok)/2;
if(mid==0) break;
for(i=1 ; i<=n ; i++){
for(j=1 ; j<=n ; j++){
// profit-Length*mid>=0
e1[i][j]=profit[i][j]-mid*min(e[i][j],val/mid);
}
}
for(i=1 ; i<=n ; i++){
for(j=1 ; j<=n ; j++){
for(q=1 ; q<=n ; q++){
e1[j][q]=max(e1[j][q],e1[j][i]+e1[i][q]);
}
}
}
bool check=0;
for(i=1 ; i<=n ; i++) if(e1[i][i]>=0) check=1;
if(check) ok=mid;
else ng=mid;
}
cout<<ok;
return 0;
}
