#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p[110][110],d[110][110],con[110][110];
ll b[110][1010],s[110][1010];
int main(){
int n,m,k; cin>>n >>m >>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
cin>>b[i][j] >>s[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) p[i][j]=0;
else{
ll mx=0;
for(int x=1;x<=k;x++){
if(b[i][x]==-1 || s[j][x]==-1) continue;
mx=max(mx,s[j][x]-b[i][x]);
}
p[i][j]=mx;
}
d[i][j]=LLONG_MAX;
}
}
for(int i=0;i<m;i++){
int u,v; ll t; cin>>u >>v >>t;
d[u][v]=min(d[u][v],t);
}
for(int x=1;x<=n;x++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(d[i][x]==LLONG_MAX || d[x][j]==LLONG_MAX) continue;
if(d[i][x]+d[x][j]<d[i][j]){
d[i][j]=d[i][x]+d[x][j];
}
}
}
}
ll l=1,r=1e9;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<d[i][j] <<" \n"[j==n];
// }
// }
while(l<r){
ll mid=(l+r+1LL)/2LL;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(d[i][j]==LLONG_MAX) con[i][j]=LLONG_MAX;
else con[i][j]=mid*d[i][j]-p[i][j];
}
}
for(int x=1;x<=n;x++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(con[i][x]==LLONG_MAX || con[x][j]==LLONG_MAX) continue;
if(con[i][x]+con[x][j]<con[i][j]){
con[i][j]=con[i][x]+con[x][j];
}
}
}
}
ll mn=LLONG_MAX;
for(int i=1;i<=n;i++) mn=min(mn,con[i][i]);
if(mn<=0) l=mid;
else r=mid-1;
}
cout<<l;
}
