#include <bits/stdc++.h>
using namespace std;
const int inf = int(1e9) + 9;
const int N = 109;
const int K = 1009;
int B[N][K];
int S[N][K];
int dist[N][N];
int prof[N][N];
long long cost[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
cin >> B[i][j] >> S[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = inf;
}
}
while (m--) {
int u, v, w;
cin >> u >> v >> w;
dist[u][v] = w;
}
for (int x = 1; x <= n; x++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int K = 1; K <= k; K++) {
if (B[i][K] != -1 && S[j][K] != -1) {
prof[i][j] = max(prof[i][j], S[j][K] - B[i][K]);
}
}
}
}
int low = 0, high = inf;
while (low <= high) {
int mid = (low + high) >> 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cost[i][j] = 1LL * mid * dist[i][j] - prof[i][j];
}
}
for (int x = 1; x <= n; x++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cost[i][j] = min(cost[i][j], cost[i][x] + cost[x][j]);
}
}
}
bool ok = false;
for (int i = 1; i <= n; i++) {
if (cost[i][i] <= 0) {
ok = true;
break;
}
}
if (ok) {
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << low - 1 << '\n';
return 0;
}
