#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, m, n) for (i32 i = (i32)(n) - 1; i >= (i32)(m); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003LL;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
} else {
return false;
}
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
} else {
return false;
}
}
bool has_cycle(i32 n, Vec<Vec<i32>> g) {
Vec<i32> deg(n);
REP(i, n) for (i32 j : g[i]) {
++deg[j];
}
queue<i32> que;
REP(i, n) {
if (deg[i] == 0) {
que.push(i);
}
}
while (!que.empty()) {
i32 v = que.front();
que.pop();
for (i32 u : g[v]) {
if (--deg[u] == 0) {
que.push(u);
}
}
}
return count(ALL(deg), 0) != n;
}
int main() {
i32 n, m, k;
cin >> n >> m >> k;
Vec<Vec<i64>> b(n, Vec<i64>(k)), s(n, Vec<i64>(k));
REP(i, n) {
REP(j, k) {
cin >> b[i][j] >> s[i][j];
}
}
Vec<Vec<pair<i32, i64>>> g(n);
REP(i, m) {
i32 u, v, t;
cin >> u >> v >> t;
--u;
--v;
g[u].emplace_back(v, t);
}
Vec<Vec<i64>> dist(n, Vec<i64>(n, INF64));
REP(i, n) {
dist[i][i] = 0;
for (auto [j, t] : g[i]) {
dist[i][j] = t;
}
}
REP(k, n) REP(i, n) REP(j, n) {
chmin(dist[i][j], dist[i][k] + dist[k][j]);
}
Vec<i32> use(n);
REP(i, n) {
use[i] = (i32)(dist[0][i] != INF64 && dist[i][0] != INF64);
}
Vec<Vec<i64>> profit(n, Vec<i64>(n, 0));
REP(i, n) REP(j, n) REP(l, k) {
if (b[i][l] != -1 && s[j][l] != -1) {
chmax(profit[i][j], s[j][l] - b[i][l]);
}
}
const auto judge = [&](i64 x) -> bool {
Vec<Vec<i64>> e(n, Vec<i64>(n, INF64));
REP(i, n) REP(j, n) if (use[i] && use[j]) {
e[i][j] = x * dist[i][j] - profit[i][j];
}
Vec<i64> d(n, INF64);
REP(iter, n) REP(i, n) REP(j, n) {
if (chmin(d[j], d[i] + e[i][j]) && iter == n - 1) {
return true;
}
}
Vec<Vec<i32>> g_(n);
REP(i, n) REP(j, n) {
if (i != j && d[i] + e[i][j] == d[j]) {
g_[i].push_back(j);
}
}
return has_cycle(n, g_);
};
i64 ok = 0, ng = 2LL * INF;
while (ng - ok > 1) {
i64 mid = (ok + ng) / 2;
if (judge(mid)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << '\n';
}
