#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e2 + 10, MAXK = 1e3 + 10; const ll INF = 2e18; ll n, m, k, d[MAXN][MAXN], best[MAXN][MAXN], b[MAXN][MAXK], s[MAXN][MAXK]; ll d1[MAXN][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++) for (int j = 0; j < n; j++) d1[i][j] = -INF; for (int i = 0; i < n; i++) { for (auto p : adj[i]) d1[i][p.first] = -x * p.second; for (int j = 0; j < n; j++) if (d[i][j] != INF && j != i) d1[i][j] = max(d1[i][j], best[i][j] - x * d[i][j]); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) for (int x = 0; x < n; x++) d1[j][x] = max(d1[j][x], d1[j][i] + d1[i][x]); for (int j = 0; j < n; j++) if (d1[j][j] >= 0) 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 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 */