#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i)
#define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
const int inf = 1e9 + 7;
const double EPS = 1e-2;
int n, m, k;
vector<vector<int>> b, s, minD, maxC;
vector<vector<pair<int, int>>> adj;
void load_minDist() {
FOR(i, 1, n) minD[i][i] = 0;
FOR(u, 1, n) FORALL(e, adj[u]) minD[u][e.fi] = min(minD[u][e.fi], e.se);
FOR(k, 1, n) FOR(i, 1, n) FOR(j, 1, n) minD[i][j] = min(minD[i][j], minD[i][k] + minD[k][j]);
}
void load_maxCost() {
FOR(i, 1, n) {
FOR(j, 1, n) {
FOR(z, 1, k) {
if (b[i][z] == - 1 || s[j][z] == - 1) continue;
maxC[i][j] = max(maxC[i][j], s[j][z] - b[i][z]);
}
}
}
}
bool check(double x) {
vector<double> f(n + 1);
FOR(t, 1, n) {
FOR(u, 1, n) FOR(v, 1, n) {
if (minD[u][v] == inf) continue;
if (f[v] > f[u] + (double)x * minD[u][v] - maxC[u][v]) f[v] = f[u] + (double)x * minD[u][v] - maxC[u][v];
}
}
REP(t, n) {
FOR(u, 1, n) FOR(v, 1, n) {
if (minD[u][v] == inf) continue;
if (f[v] > f[u] + (double)x * minD[u][v] - maxC[u][v]) return true;
}
}
return false;
}
int main() {
fastio;
cin >> n >> m >> k;
b.assign(n + 1, vector<int>(k + 1));
s.assign(n + 1, vector<int>(k + 1));
FOR(i, 1, n) FOR(j, 1, k) cin >> b[i][j] >> s[i][j];
adj.resize(n + 1);
REP(i, m) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
minD.assign(n + 1, vector<int>(n + 1, inf));
load_minDist();
maxC.assign(n + 1, vector<int>(n + 1));
load_maxCost();
double l = 0;
double r = inf;
while (l + EPS <= r) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
cout << (int)(l + EPS) << '\n';
return 0;
}
