#include <iostream>
using namespace std;
long long n,k,m;
long long buy[105][1005], sell[105][1005];
long long dist[105][105];
long long val[105][105];
long long distMax[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 calcProfit()
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n ; j++)
{
if(i == j)
continue;
val[i][j] = 0;
for(int produs=1; produs<=k; produs++)
val[i][j] = max(val[i][j], -buy[i][produs] + sell[j][produs]);
}
}
bool ok(long long x)
{
distMax[1] = 0;
for(int i=2;i<=n;i++)
distMax[i] = -1e18;
int aux = n;
while(aux)
{
aux --;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i == j)
continue;
long long l = val[i][j] - dist[i][j] * x;
if(distMax[j] < distMax[i] + l)
{
if(!aux)
return true;
distMax[j] = distMax[i] + l;
}
}
}
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];
if(buy[i][j] == -1)
buy[i][j] = 1e9;
if(sell[i][j])
sell[i][j] = - 1e9;
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(i == j)
continue;
dist[i][j] = 1e9;
}
for(int i=1; i<=m; i++)
{
long long x, y, val;
cin>>x>>y>>val;
dist[x][y] = min(dist[x][y], val);
}
calcDist();
calcProfit();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<dist[i][j]<<' ';
cout<<'\n';
}
return 0;
long long st, dr, mij, last=0;
st=0;
dr=1e9;
while(st <= dr)
{
mij = (st+dr)/2;
if(ok(mij))
{
last=mij;
st=mij+1;
}
else
dr=mij-1;
}
cout<<last;
return 0;
}
