#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define fi first
#define se second
using ll = long long;
const int maxn = (int)1e2+10;
const ll LINF = (ll)1e18;
int n, m, k;
int a[maxn][maxn][2];
int dis[maxn][maxn];
vector<pair<int,int>> adj[maxn];
int32_t main()
{
int n, m, k, ans = 0, path=LINF;
cin >> n >> m >> k;
for(int i = 0; i < n; i++)
for(int j = 0; j < k; j++)
cin >> a[i][j][0] >> a[i][j][1];
for(int i = 0; i < n; i++)
fill(dis[i],dis[i]+maxn,LINF);
for(int i = 0; i < m; i++){
int a, b, c; cin >> a >> b >> c; a--, b--;
adj[a].pb({b,c}); dis[a][b]=c;
}
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
for(int j = 0; j < k; j++)
if(a[0][j][0]!=-1 and a[0][j][1]!=-1)
ans+=max(0ll, a[0][j][1]-a[0][j][0]);
for(int i = 1; i < n; i++){
bool ok = 0; int cost=0;
for(auto u : adj[i]) if(u.fi==0) ok=1,cost=u.se;
if(ok) path = min(path, dis[0][i]+cost);
}
cout << ans/path;
}
