#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using ll = long long;
#define debug(x) #x << " = " << x << '\n'
#define int ll
const ll INF = 1e18;
signed 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));
std::vector<std::vector<int>> sell(n, std::vector<int>(k));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
std::cin >> buy[i][j] >> sell[i][j];
}
}
std::vector<std::vector<int>> dist(n, std::vector<int>(n, (int) +INF));
for (int i = 0; i < m; i++) {
int u, v, w;
std::cin >> u >> v >> w;
u--, v--;
dist[u][v] = std::min(dist[u][v], w);
}
for (int k = 0; k < n; k++) {
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
dist[u][v] = std::min(dist[u][v], dist[u][k] + dist[k][v]);
}
}
}
std::vector<std::vector<int>> profit(n, std::vector<int>(n, 0));
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
for (int i = 0; i < k; i++) {
profit[u][v] = 0;
if (buy[u][i] != -1 && sell[v][i] != -1) {
profit[u][v] = std::max(profit[u][v], sell[v][i] - buy[u][i]);
}
}
}
}
auto check = [&](int mid) {
std::vector<std::vector<ll>> cost(n, std::vector<ll>(n, +INF));
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (dist[u][v] < +INF) {
if ((ll) dist[u][v] <= INF / mid) {
cost[u][v] = (ll) dist[u][v] * mid - profit[u][v];
}
}
}
}
for (int k = 0; k < n; k++) {
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
cost[u][v] = std::min(cost[u][v], cost[u][k] + cost[k][v]);
cost[u][v] = std::max(cost[u][v], -INF);
}
}
}
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (cost[u][v] + cost[v][u] <= 0) {
return true;
}
}
}
return false;
};
int l = 0, r = 1e18;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
std::cout << r;
return 0;
}
