#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 1004
#define INF 1e9+7
using namespace std;
ll n,m,k,u,v,t,ans;
ll buy[N][N];
ll sell[N][N];
ll dist[N][N],cost[N][N],test[N][N];
bool can(ll x)
{
rep(i,0,n)
{
rep(j,0,n)
{
if(dist[i][j] != INF && x*dist[i][j] - cost[i][j] < INF)
test[i][j] = cost[i][j] - x*dist[i][j];
else
test[i][j] = -INF;
}
}
rep(p,0,n)
{
rep(i,0,n)
{
rep(j,0,n)
{
if(test[i][p] <= -INF || test[p][j] <= -INF)
continue;
test[i][j] = max(test[i][j],test[i][p] + test[p][j]);
}
}
}
rep(i,0,n)
{
if(test[i][i] >= 0)
return true;
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n >> m >> k;
rep(j,0,n)
{
rep(i,0,k)
{
cin >> buy[i][j] >> sell[i][j];
}
}
rep(i,0,n)
{
rep(j,0,n)
{
dist[i][j] = INF;
}
}
rep(i,0,m)
{
cin >> u >> v >> t;
u--;
v--;
dist[u][v] = t;
}
rep(p,0,n)
{
rep(i,0,n)
{
rep(j,0,n)
{
dist[i][j] = min(dist[i][j],dist[i][p] + dist[p][j]);
}
}
}
rep(i,0,n)
{
rep(j,0,n)
{
if(dist[i][j] == INF)
continue;
rep(p,0,k)
{
if(buy[p][i] != -1 && sell[p][j] != -1)
cost[i][j] = max(cost[i][j],-buy[p][i] + sell[p][j]);
}
}
}
ll low = 0;
ll high = 1000000001;
ll ans = 0;
while(low < high)
{
ll mid = (low + high) / 2;
if(can(mid))
{
ans = max(ans,mid);
low = mid+1;
}
else
{
high = mid-1;
}
}
while(can(ans+1))
ans++;
cout << ans << endl;
return 0;
}
