#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];
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)
{
/*
cout<<'\n';
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
long long nval = prof[i][j] - x * dist[i][j];
cout<<nval<<' ';
}
cout<<'\n';
}
cout<<"\n\n";
*/
for(int rad=1; rad<=n; rad++)
{
for(int i=1; i<=n; i++)
profMax[i] = -1e18;
profMax[rad] = 0;
for(int nr=1; nr<n; nr++)
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(i == j)
continue;
long long nval = prof[i][j] - x * dist[i][j];
nval += profMax[i];
if(nval > profMax[j])
profMax[j] = nval;
}
}
for(int i=1;i<=n;i++)
{
if(i == rad)
continue;
long long nval = prof[i][rad] - x * dist[i][rad];
nval += profMax[i];
if(nval >= 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;
dist[i][i] = 0;
}
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();
//cout<<ok(3);
//return 0;
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;
}
