#include <bits/stdc++.h>
using namespace std;
#define MAXN 101
#define MAXM 1001
#define int long long
int n,m,k;
int buy[MAXN][MAXM],sell[MAXN][MAXM];
int adj[2][MAXN][MAXN],profit[MAXN][MAXN];
bool check(int mid)
{
for (int node1=1;node1<=n;node1++)
{
for (int node2=1;node2<=n;node2++) adj[1][node1][node2]=mid*min(adj[0][node1][node2],LLONG_MAX/mid)-profit[node1][node2];
}
for (int node=1;node<=n;node++)
{
for (int node1=1;node1<=n;node1++)
{
for (int node2=1;node2<=n;node2++)
{
if (adj[1][node1][node]==LLONG_MAX or adj[1][node][node2]==LLONG_MAX) continue;
adj[1][node1][node2]=min(adj[1][node1][node2],adj[1][node1][node]+adj[1][node][node2]);
}
}
}
for (int node=0;node<=n;node++)
{
if (adj[1][node][node]<0) return false;
}
return true;
}
int32_t main()
{
cin>>n>>m>>k;
for (int node=1;node<=n;node++)
{
for (int item=1;item<=k;item++) cin>>buy[node][item]>>sell[node][item];
for (int sled=1;sled<=n;sled++) adj[0][node][sled]=LLONG_MAX;
}
for (int i=1;i<=m;i++) {int node1,node2,time;cin>>node1>>node2>>time;adj[0][node1][node2]=time;}
for (int node=1;node<=n;node++)
{
for (int node1=1;node1<=n;node1++)
{
for (int node2=1;node2<=n;node2++)
{
if (adj[0][node1][node]==LLONG_MAX or adj[0][node][node2]==LLONG_MAX) continue;
adj[0][node1][node2]=min(adj[0][node1][node2],adj[0][node1][node]+adj[0][node][node2]);
}
}
}
for (int node1=1;node1<=n;node1++)
{
for (int node2=1;node2<=n;node2++)
{
for (int item=1;item<=k;item++)
{
if (buy[node1][item]==-1 or sell[node2][item]==-1) continue;
profit[node1][node2]=max(profit[node1][node2],sell[node2][item]-buy[node1][item]);
}
}
}
int l=1,r=INT_MAX,rez=0;
while (l<=r)
{
int mid=(l+r)/2;
if (check(mid)) {rez=mid;r=mid-1;}
else l=mid+1;
}
cout<<rez<<endl;
}
