#include <iostream>
#pragma GCC optimize ("unroll-loops")
using namespace std;
long long n,m,k;
long long dist[105][105];
long long buy[105][1005], sell[105][1005];
long long prof[105][105];
long long profMax[105][105];
void calcDist()
{
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
void calcProf()
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
prof[i][j] = 0;
for(int nr=1; nr<=k; nr++)
if(buy[i][nr] != -1 && sell[j][nr] != -1)
prof[i][j] = max(prof[i][j], sell[j][nr] - buy[i][nr]);
}
}
bool ok(long long x)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
profMax[i][j] = x * min(dist[i][j], (long long)1e18 / x) - prof[i][j];
for(int k=1; k<=n; k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
profMax[i][j] = min(profMax[i][j], profMax[i][k] + profMax[k][j]);
for(int i=1;i<=n;i++)
if(profMax[i][i] <= 0)
return true;
return false;
}
int main()
{
cin>>n>>m>>k;
for(int i=1; i<=n; i++)
for(int j=1; j<=k; j++)
cin>>buy[i][j]>>sell[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dist[i][j] = 1e18;
for(int i=1; i<=m; i++)
{
long long x, y, w;
cin>>x>>y>>w;
dist[x][y] = min(dist[x][y], w);
}
calcDist();
calcProf();
long long st=0, dr=1e9, mij, last=0;
while(st <= dr)
{
mij = (st+dr)/2;
if(ok(mij))
{
last = mij;
st = mij+1;
}
else
dr = mij-1;
}
cout<<last;
return 0;
}
