#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mxn = 105;
const ll mxk = 1005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll dist[mxn][mxn];
ll best[mxn][mxn];
ll trmp[mxn][mxn];
ll b[mxn][mxk];
ll s[mxn][mxk];
ll n, m, k;
void floyd_warshall(ll d[mxn][mxn]) {
for (ll k = 1; k <= n; k++) {
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
bool chk(ll m) {
memset(trmp, 0x3f, sizeof(trmp));
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= n; j++) {
if (i != j && dist[i][j] != inf) {
trmp[i][j] = dist[i][j] * m - best[i][j];
}
}
}
floyd_warshall(trmp);
for (ll i = 1; i <= n; i++) {
if (trmp[i][i] <= 0) return true;
}
return false;
}
int main() {
(void)!scanf("%lld%lld%lld", &n, &m, &k);
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= k; j++) {
(void)!scanf("%lld%lld", &b[i][j], &s[i][j]);
}
}
memset(dist, 0x3f, sizeof(dist));
for (ll i = 1; i <= m; i++) {
ll v, w, t;
(void)!scanf("%lld%lld%lld", &v, &w, &t);
dist[v][w] = min(dist[v][w], t);
}
floyd_warshall(dist);
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= n; j++) {
for (ll p = 1; p <= k; p++) {
if (b[i][p] != -1 && s[j][p] != -1) {
best[i][j] = max(best[i][j], s[j][p] - b[i][p]);
}
}
}
}
ll l = 0, r = 2e9;
while (r - l > 1) {
m = l + (r - l) / 2;
if (chk(m)) l = m;
else r = m;
}
printf("%lld\n", l);
}
