#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
void BF(vector<vector<ll>>& dis) {
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]);
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int m, K;
cin >> n >> m >> K;
vector<vector<int>> B(n, vector<int>(K)), S = B;
for (int i = 0; i < n; i++) {
for (int j = 0; j < K; j++)
cin >> B[i][j] >> S[i][j];
}
vector<vector<ll>> dis(n, vector<ll>(n, (ll)1e18));
while (m--) {
int x, y, w;
cin >> x >> y >> w; x--; y--;
dis[x][y] = w;
}
BF(dis);
vector<vector<int>> pr(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < K; k++)
if (~B[i][k] && ~S[j][k]) pr[i][j] = max(pr[i][j], S[j][k] - B[i][k]);
}
}
int l = 1, r = (int)1e9;
while (l <= r) {
int md = (l + r) >> 1;
vector<vector<ll>> d(n, vector<ll>(n, (ll)1e18));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
d[i][j] = (ll)md * min((ll)1e18 / md, dis[i][j]) - pr[i][j];
}
BF(d);
bool tr = false;
for (int i = 0; i < n && !tr; i++)
tr = d[i][i] <= 0;
if (tr) l = md + 1;
else r = md - 1;
}
cout << l - 1;
}
