#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long inf=4e18;
long long n, m, K;
long long b[105][1005], s[105][1005];
long long vreme[105][105];
long long val[105][105];
long long ed[105][105];
long long distc[105][105];
bool pos(long long x)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(vreme[i][j]!=inf) ed[i][j]=x*vreme[i][j]-val[i][j];
else ed[i][j]=inf;
distc[i][j]=ed[i][j];
}
}
for(int i=1; i<=n; i++) distc[i][i]=0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(i==j) continue;
if(distc[i][j]+distc[j][i]<=0) return 1;
}
}
return 0;
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(distc[i][k]==inf || distc[k][j]==inf) continue;
if(distc[i][k]+distc[k][j]<distc[i][j]) distc[i][j]=distc[i][k]+distc[k][j];
}
}
}
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(distc[i][k]==inf || distc[k][j]==inf) continue;
if(distc[i][k]+distc[k][j]<distc[i][j]) return 1;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>K;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=K; j++)
{
cin>>b[i][j]>>s[i][j];
if(b[i][j]==-1) b[i][j]=inf;
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++) vreme[i][j]=inf;
vreme[i][i]=0;
}
for(int i=0; i<m; i++)
{
int u, v, d;
cin>>u>>v>>d;
vreme[u][v]=d;
}
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(vreme[i][k]+vreme[k][j]<vreme[i][j]) vreme[i][j]=vreme[i][k]+vreme[k][j];
}
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
for(int t=1; t<=K; t++) if(val[i][j]<s[j][t]-b[i][t]) val[i][j]=s[j][t]-b[i][t];
}
}
long long le=0, ri=1e9+1;
while(ri-le>1)
{
long long mid=(le+ri)/2;
if(pos(mid)) le=mid;
else ri=mid;
}
cout<<le<<endl;
return 0;
}
/**
4 5 2
10 9 5 -1
6 4 20 -1
9 7 10 -1
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/
