/* Author: goats_9 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1e18;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<ll>> b(n, vector<ll> (k));
auto s = b;
for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> b[i][j] >> s[i][j];
vector<vector<ll>> p(n, vector<ll> (n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int z = 0; z < k; z++) {
if (b[i][z] != -1 && s[j][z] != -1) p[i][j] = max(p[i][j], s[j][z] - b[i][z]);
}
}
}
vector<vector<pair<int, ll>>> g(n);
vector<vector<ll>> d(n, vector<ll> (n, INF));
for (int i = 0; i < m; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
g[--u].emplace_back(--v, w);
d[u][v] = w;
}
for (int z = 0; z < n; z++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = min(d[i][j], d[i][z] + d[z][j]);
}
}
}
ll l = 0, r = 1e9;
while (r - l > 1) {
ll x = (l + r) / 2;
vector<vector<ll>> dp(n, vector<ll> (n, INF));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (d[i][j] < INF) dp[i][j] = min(dp[i][j], d[i][j] * x - p[i][j]);
}
}
for (int z = 0; z < n; z++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dp[i][j] = min(dp[i][j], dp[i][z] + dp[z][j]);
bool ok = false;
for (int i = 0; i < n; i++) if (dp[i][i] <= 0) ok = true;
if (ok) l = x;
else r = x;
}
cout << l;
return 0;
}
