#include <bits/stdc++.h>
using namespace std;
long long const INF=1e18;
int const MAX=105;
int n,m,prod;
long long buy[MAX][1005];
long long sell[MAX][1005];
long long path[MAX][MAX];
long long profit[MAX][MAX];
void read(){
cin>>n>>m>>prod;
int i,j;
for(i=1;i<=n;++i)
for(j=1;j<=prod;++j)
cin>>buy[i][j]>>sell[i][j];
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
path[i][j]=INF;
for(i=1;i<=m;++i){
int u,v,w;
cin>>u>>v>>w;
path[u][v]=w;
}
}
void minself(long long& x,long long val){
if(x>val)
x=val;
}
void maxself(long long& x,long long val){
if(x<val)
x=val;
}
void roy_floyd(long long mat[][MAX]){
int i,j,k;
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
minself(mat[i][j],mat[i][k]+mat[k][j]);
}
void get_profit(){
int i,j,k;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
for(k=1;k<=prod;++k)
if(buy[i][k]!=-1 && sell[j][k]!=-1)
maxself(profit[i][j],sell[j][k]-buy[i][k]);
}
}
long long way[MAX][MAX];
bool check(int rasp){
int i,j;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(path[i][j]<INF)
way[i][j]=path[i][j]*rasp-profit[i][j];
else
way[i][j]=INF;
roy_floyd(way);
for(i=1;i<=n;++i)
if(way[i][i]<=0)
return 1;
return 0;
}
int bin_search(){
/// [)
int st=0,dr=1e9;
while(dr-st>1){
int mij=(st+dr)/2;
if(check(mij))
st=mij;
else
dr=mij;
}
return st;
}
int main()
{
read();
roy_floyd(path);
get_profit();
cout<<bin_search();
return 0;
}
