#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using ll = long long;
#define debug(x) #x << " = " << x << '\n'
const ll INF = 1e18;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n, m, k;
std::cin >> n >> m >> k;
std::vector<std::vector<int>> buy(n, std::vector<int>(k + 1));
std::vector<std::vector<int>> sell(n, std::vector<int>(k + 1));
for (int i = 0; i < n; i++) {
for (int j = 1; j <= k; j++) {
std::cin >> buy[i][j] >> sell[i][j];
}
}
std::vector<std::vector<std::pair<int, int>>> g(n);
std::vector<std::vector<std::pair<int, int>>> gg(n);
for (int i = 0; i < m; i++) {
int u, v, t;
std::cin >> u >> v >> t;
u--, v--;
g[u].push_back({v, t});
gg[v].push_back({u, t});
}
auto check = [&](int root, int mid) {
std::vector<std::vector<ll>> d(n, std::vector<ll>(k + 1, +INF));
d[root][0] = 0;
bool repeat = true;
for (int _ = 0; _ < 50 && repeat; _++) {
repeat = false;
for (int u = 0; u < n; u++) {
for (int i = 1; i <= k; i++) {
if (sell[u][i] != -1 && d[u][i] + -sell[u][i] < d[u][0]) {
d[u][0] = d[u][i] - sell[u][i];
repeat = true;
}
if (buy[u][i] != -1 && d[u][0] + buy[u][i] < d[u][i]) {
d[u][i] = d[u][0] + buy[u][i];
repeat = true;
}
}
for (int i = 0; i <= k; i++) {
for (auto [v, t] : g[u]) {
ll w = (ll) mid * t;
if (d[u][i] + w < d[v][i]) {
d[v][i] = d[u][i] + w;
repeat = true;
}
}
}
}
}
if (repeat) {
return true;
}
for (auto [u, t] : gg[root]) {
ll w = (ll) mid * t;
if (d[u][0] + w <= 0) {
return true;
}
for (int i = 1; i <= k; i++) {
if (sell[root][i] != -1 && d[u][i] + w + -sell[root][i] <= 0) {
return true;
}
}
}
return false;
};
int answer = 0;
for (int root = 0; root < n; root++) {
if (check(root, answer)) {
int l = answer, r = 1e9;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(root, mid)) {
l = mid;
} else {
r = mid - 1;
}
}
answer = r;
}
}
std::cout << answer;
return 0;
}
