#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 105, K = 1005;
const ll inf = 1e18;
array<ll, 2> a[N][K];
ll dist[N][N], dist2[N][N], dist3[N][N], c[N][N];
int n, m, t;
bool check(ll v) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist2[i][j] = -1e18;
for (int k = 1; k <= n; k++) {
if (dist[i][k] + dist3[k][j] <= inf / v) {
// if (i == 1 && j == 1) {
// cout << -(dist[i][k] + dist3[k][j]) * v + c[k][j] << ' ' << k << ' ' << c[k][j] << ' ' << dist[i][k] << ' ' << dist3[k][j] << '\n';
// }
dist2[i][j] = max(dist2[i][j], -(dist[i][k] + dist3[k][j]) * v + c[k][j]);
}
}
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist2[i][j] = max(dist2[i][j], dist2[i][k] + dist2[k][j]);
}
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist2[i][k] + dist2[k][j] > dist2[i][j]) {
dist2[i][j] = 1e18;
}
}
}
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// cout << dist2[i][j] << ' ';
// }
// cout << '\n';
// }
// cout << dist[1][2] << ' ' << dist[3][1] << ' ' << dist2[2][3] << '\n';
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (dist[i][j] + dist[k][i] <= inf / v) {
if (dist2[j][k] - (dist[i][j] + dist[k][i]) * v >= 0) {
// cout << i << ' ' << j << ' ' << k << ' ' << i << ": " << dist2[j][k] << ' ' << dist[i][j] << ' ' << dist[k][i] << '\n';
return 1;
}
}
}
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> t;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < t; j++) {
cin >> a[i][j][0] >> a[i][j][1];
if (a[i][j][0] == -1) {
a[i][j][0] = 1e18;
}
if (a[i][j][1] == -1) {
a[i][j][1] = -1e18;
}
}
}
memset(dist, '?', sizeof dist);
memset(dist3, '?', sizeof dist3);
for (int i = 0, u, v, w; i < m; i++) {
cin >> u >> v >> w;
dist[u][v] = w;
dist3[u][v] = w;
}
for (int i = 1; i <= n; i++) {
dist[i][i] = 0;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
dist3[i][j] = min(dist3[i][j], dist3[i][k] + dist3[k][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
c[i][j] = -1e18;
// buy at i, sell at j
for (int k = 0; k < t; k++) {
// if (i == 4 && j == 1) {
// cout << - a[i][k][0] + a[j][k][1] << '\n';
// }
c[i][j] = max(c[i][j], - a[i][k][0] + a[j][k][1]);
}
}
}
ll l = 1, r = 1e18;
while (l <= r) {
ll md = ((l + r) >> 1);
if (check(md)) {
l = md + 1;
} else {
r = md - 1;
}
}
cout << r << '\n';
return 0;
}
