#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
using ull = unsigned long long;
using ll = long long;
using namespace std;
constexpr ll INF = (ll) 1e18;
int main() {
#ifdef HOME
ifstream cin("input.in");
ofstream cout("output.out");
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> buy(n + 1, vector<int>(k + 1));
vector<vector<int>> sell(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
cin >> buy[i][j] >> sell[i][j];
}
}
vector<vector<pair<int, int>>> g(n + 1);
while (m--) {
int x, y, z;
cin >> x >> y >> z;
g[x].push_back({y, z});
}
auto Check = [&](ll C) {
for (int source = 1; source <= n; source++) {
queue<pair<int, int>> Q;
Q.push({source, 0});
vector<vector<bool>> inQ(n + 1, vector<bool>(k + 1));
inQ[source][0] = true;
vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, -INF));
dp[source][0] = 0;
vector<vector<int>> cnt(n + 1, vector<int>(k + 1));
vector<bool> mark(n + 1);
auto Go = [&](int node, int item, ll cost) {
if (cost > dp[node][item]) {
dp[node][item] = cost;
if (!inQ[node][item]) {
Q.push({node, item});
inQ[node][item] = true;
}
} else if (cost == dp[node][item]) {
mark[node] = true;
}
};
while (Q.size()) {
int node, item;
tie(node, item) = Q.front();
Q.pop();
inQ[node][item] = false;
cnt[node][item]++;
if (cnt[node][item] >= n * k) {
return true;
}
for (auto edge : g[node]) {
Go(edge.first, item, dp[node][item] - 1LL * edge.second * C);
}
if (item == 0) {
for (int new_item = 1; new_item <= k; new_item++) {
if (buy[node][new_item] != -1) {
Go(node, new_item, dp[node][0] - buy[node][new_item]);
}
}
} else {
if (sell[node][item] != -1) {
Go(node, 0, dp[node][item] + sell[node][item]);
}
}
}
if (dp[source][0] > 0 || (dp[source][0] == 0 && mark[source])) {
return true;
}
// cerr << "source: " << source << "\n";
// for (int i = 1; i <= n; i++) {
// for (int j = 0; j <= k; j++) {
// cerr << dp[i][j] << " ";
// }
// cerr << "\n";
// }
// cerr << "\n";
}
return false;
};
ll result = 0;
for (ll step = 1LL << 30; step; step >>= 1) {
if (Check(result + step)) {
result += step;
}
}
cout << result;
return 0;
}
