#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
const __int128_t INF = 5e18;
struct Edge {
int to;
__int128_t length, profit;
};
int main() {
int n, m, k;
std::cin >> n >> m >> k;
std::vector<std::vector<long long>> b(n, std::vector<long long>(k)), s(n, std::vector<long long>(k));
for (int i = 0; i < n; ++i) {
for (int item = 0; item < k; ++item) std::cin >> b[i][item] >> s[i][item];
}
std::vector<std::vector<Edge>> adj(n);
while (m--) {
int u, v;
long long t;
std::cin >> u >> v >> t;
--u, --v;
adj[u].emplace_back(v, t, 0);
}
std::vector<std::vector<__int128_t>> shortestPath(n, std::vector<__int128_t>(n));
for (int i = 0; i < n; ++i) {
std::priority_queue<std::pair<__int128_t, int>> q;
std::vector<int> seen(n);
q.emplace(0, i);
while (!q.empty()) {
auto [d, node] = q.top();
q.pop();
if (seen[node]) continue;
shortestPath[i][node] = -d;
seen[node] = true;
for (auto e : adj[node]) {
q.emplace(d - e.length, e.to);
}
}
}
for (int i = 0; i < n; ++i) {
for (int f = 0; f < n; ++f) {
if (i == f) continue;
long long max = 0;
for (int item = 0; item < k; ++item) {
if (b[i][item] == -1 || s[f][item] == -1) continue;
max = std::max(max, s[f][item] - b[i][item]);
}
adj[i].emplace_back(f, shortestPath[i][f], max);
}
}
long long lo = 0, hi = 1e18;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
std::vector<std::vector<__int128_t>> floyd(n, std::vector<__int128_t>(n, -INF)); // longest path
for (int i = 0; i < n; ++i) {
for (auto [to, dist, profit] : adj[i]) floyd[i][to] = profit - mid * dist;
}
for (int kk = 0; kk < n; ++kk) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
floyd[i][j] = std::max(floyd[i][j], floyd[i][kk] + floyd[kk][j]);
}
}
}
bool exists = false;
for (int i = 0; i < n; ++i) exists |= (floyd[i][i] >= 0);
if (exists) {
lo = mid;
} else {
hi = mid - 1;
}
}
std::cout << lo << '\n';
return 0;
}
