#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int MAXN = 1e2 + 10, MAXK = 1e3 + 10; const ll INF = 4e18; ll n, m, k, d[MAXN][MAXN], best[MAXN][MAXN], b[MAXN][MAXK], s[MAXN][MAXK]; ll d1[MAXN], d2[MAXN]; ld d3[MAXN], d4[MAXN]; vector<pair<ll, ll>> adj[MAXN]; void input() { cin >> n >> m >> k; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = INF; for (int i = 0; i < n; i++) d[i][i] = 0; for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> b[i][j] >> s[i][j]; for (int i = 0; i < m; i++) { ll u, v, w; cin >> u >> v >> w; d[--u][--v] = w; adj[u].push_back({v, w}); } } void findDist() { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int x = 0; x < n; x++) d[j][x] = min(d[j][x], d[j][i] + d[i][x]); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int x = 0; x < k; x++) if (b[i][x] != -1 && s[j][x] != -1) best[i][j] = max(best[i][j], s[j][x] - b[i][x]); } bool check(ll x) { for (int i = 0; i < n; i++) d1[i] = d2[i] = 0; for (int i = 0; i < 2 * n; i++) { for (int j = 0; j < n; j++) { for (auto p : adj[j]) d1[p.first] = max(d1[p.first], d1[j] - x * p.second); for (int y = 0; y < n; y++) if (d[j][y] != INF) d1[y] = max(d1[y], d1[j] + best[j][y] - x * d[j][y]); } if (i == (n - 1)) { for (int j = 0; j < n; j++) d2[j] = d1[j]; } } for (int i = 0; i < n; i++) if (d1[i] != d2[i]) return true; return false; } bool check1(ld x) { for (int i = 0; i < n; i++) d3[i] = d4[i] = 0; for (int i = 0; i < 2 * n; i++) { for (int j = 0; j < n; j++) { for (auto p : adj[j]) d3[p.first] = max(d3[p.first], d3[j] - x * p.second); for (int y = 0; y < n; y++) if (d[j][y] != INF) d3[y] = max(d3[y], d3[j] + best[j][y] - x * d[j][y]); } if (i == (n - 1)) { for (int j = 0; j < n; j++) d4[j] = d3[j]; } } for (int i = 0; i < n; i++) if (d3[i] != d4[i]) return true; return false; } ll findAns() { ll l = 0, r = 1e9; while (r - l > 1) { ll mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } return (check1((ld)r - (1e-18))? r: l); } int main() { ios::sync_with_stdio(false); cin.tie(0); input(); findDist(); cout << findAns() << endl; return 0; } /* 4 5 2 10 9 5 2 6 4 20 15 9 7 10 9 -1 -1 16 11 1 2 3 2 3 3 1 4 1 4 3 1 3 1 1 */