#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 1e18 + 19999999;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, k;
std::cin >> n >> m >> k;
std::vector<std::vector<i64>> e(n, std::vector<i64>(n, inf)), prof(n, std::vector<i64>(n, 0));
std::vector<std::vector<i64>> b(n, std::vector<i64>(k)), s(n, std::vector<i64>(k));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++)
std::cin >> b[i][j];
for (int j = 0; j < k; j++)
std::cin >> s[i][j];
}
for (int i = 0; i < m; i++) {
int u, v, w;
std::cin >> u >> v >> w;
u--;
v--;
e[u][v] = std::min(e[u][v], i64(w));
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
e[i][j] = std::min(e[i][j], e[i][k] + e[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int c = 0; c < k; c++) {
if (~b[i][c] && ~s[j][c]) {
prof[i][j] = std::max(prof[i][j], s[j][c] - b[i][c]);
}
}
}
}
auto check = [&](int times) -> bool {
std::vector<std::vector<i64>> a(n, std::vector<i64>(n, -inf));
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (prof[i][j] > 0)
a[i][j] = std::max(a[i][j], prof[i][j] - e[i][j] * times);
}
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = std::max(a[i][j], a[i][k] + a[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
if (a[i][i] >= 0) {
return true;
}
}
return false;
};
int l = -1, r = 1e9 + 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
std::cout << l << '\n';
return 0;
}
