#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=110;
const ll maxk=1010;
ll n,m,k;
ll b[maxn][maxk];
ll s[maxn][maxk];
ll g[maxn][maxn];
ll newgt[maxn][maxn];
ll newgp[maxn][maxn];
ll checkg[maxn][maxn];
ll newcheckg[maxn][maxn];
void init(){
for(auto &i:g) for(auto &j:i) j=-1;
for(auto &i:newgt) for(auto &j:i) j=-1;
}
void floyd(ll g[maxn][maxn],ll res[maxn][maxn]){
for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) res[i][j]=g[i][j];
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
for(ll k=0;k<n;k++){
if(res[j][i]==-1) continue;
if(res[i][k]==-1) continue;
res[j][k]=min(res[j][k]==-1 ? INT_MAX:res[j][k],res[j][i]+res[i][k]);
}
}
}
}
bool check(ll eff){
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
checkg[i][j]=-1;
if(newgt[i][j]==-1) continue;
checkg[i][j]=eff*newgt[i][j]-newgp[i][j];
}
}
floyd(checkg,newcheckg);
for(ll i=0;i<n;i++){
if(newcheckg[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]>>s[i][j];
}
for(ll i=0;i<m;i++){
ll v,w,t;
cin>>v>>w>>t;
v--,w--;
g[v][w]=min(t,g[v][w]==-1 ? INT_MAX:g[v][w]);
}
floyd(g,newgt);
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
ll p=0;
for(ll l=0;l<k;l++){
if(s[j][l]==-1 || b[i][l]==-1) continue;
p=max(p,s[j][l]-b[i][l]);
}
newgp[i][j]=p;
}
}
/*for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
cout<<newgt[i][j]<<" ";
}
cout<<"\n";
}cout<<"\n";
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
cout<<newgp[i][j]<<" ";
}
cout<<"\n";
}*/
ll l=0,r=INT_MAX,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;
}
