#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 2e9 + 7;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> buy(n, vector<int> (k)), sell(n, vector<int> (k)), d(n, vector<int> (n, inf)), profit(n, vector<int> (n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
cin >> buy[i][j] >> sell[i][j];
}
}
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
--u, --v;
d[u][v] = c;
}
for (int w = 0; w < n; w++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = min(d[i][j], d[i][w] + d[w][j]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
for (int w = 0; w < k; w++) {
if (buy[i][w] != -1 && sell[j][w] != -1) {
profit[i][j] = max(profit[i][j], sell[j][w] - buy[i][w]);
}
}
}
}
int l = 0, r = inf;
while (l + 1 < r) {
int m = (l + r) / 2;
vector<vector<int>> edges(n, vector<int> (n, inf));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
edges[i][j] = min(edges[i][j], m * d[i][j] - profit[i][j]);
}
}
auto cost = edges;
for (int w = 0; w < n; w++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cost[i][j] = min(cost[i][j], cost[i][w] + cost[w][j]);
}
}
}
bool cycle = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
cycle |= (cost[i][j] + edges[j][i]) <= 0;
}
}
if (cycle) {
l = m;
} else {
r = m;
}
}
cout << l;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
