#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF=LLONG_MAX/2;
int n, m, x;
ll b[101][1001], s[101][1001], g[101][101], g2[101][101], p[101][101];
void floyd_warshall(ll v[101][101]){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
v[j][k]=min(v[j][k],v[j][i]+v[i][k]);
}
int main(){
iostream::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>x;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
g[i][j]=INF;
for(int j=1;j<=x;j++)
cin>>b[i][j]>>s[i][j];
}
int u, v, c;
for(int i=1;i<=m;i++){
cin>>u>>v>>c;
g[u][v]=c;
}
floyd_warshall(g);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=x;k++)
if(b[i][k]!=-1&&s[j][k]!=-1)
p[i][j]=max(p[i][j],s[j][k]-b[i][k]);
ll l=1, r=1e9;
while(l<=r){
ll mid=(l+r)/2;
cout<<mid<<endl;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g2[i][j]=mid*min(g[i][j],INF/mid)-p[i][j];
floyd_warshall(g2);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<g2[i][j]<<' ';
cout<<endl;
}
bool ciclu=0;
for(int i=1;i<=n;i++)
if(g2[i][i]<=0)
ciclu=1;
if(ciclu)
l=mid+1;
else
r=mid-1;
}
cout<<r;
return 0;
}
