// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; using ll = long long; using db = double; #define eb emplace_back const ll cap = 101; vector<pair<ll,ll>> adj[cap]; vector<pair<ll,ll>> radj[cap]; ll dist1[cap]; ll distto1[cap]; priority_queue<pair<ll,ll>> pq, revpq; void normdijkstra(ll st){ pq.push({0,st}); dist1[st] = 0; while (!pq.empty()){ auto [d, u] = pq.top(); pq.pop(); d *= -1; for (auto [s, w]: adj[u]){ if (dist1[u] + w < dist1[s]){ dist1[s] = dist1[u]+w; pq.push({-dist1[s], s}); } } } } void revdijkstra(ll st){ revpq.push({0,st}); distto1[st] = 0; while (!revpq.empty()){ auto [d, u] = revpq.top(); revpq.pop(); d *= -1; for (auto [s, w]: radj[u]){ if (distto1[u]+w < distto1[s]){ distto1[s] = distto1[u]+w; revpq.push({-distto1[s], s}); } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, m, k; cin >> n >> m >> k; vector<vector<ll>> b(n+1, vector<ll>(k+1)); vector<vector<ll>> s(n+1, vector<ll>(k+1)); fill(dist1, dist1+cap, 1e18); fill(distto1, distto1+cap, 1e18); for (ll i{}; i < n; i++){ for (ll j{}; j < k; j++){ cin >> b[i+1][j+1] >> s[i+1][j+1]; } } for (ll i{}; i < m; i++){ ll x, y, w; cin >> x >> y >> w; adj[x].eb(y, w); radj[y].eb(x, w); } normdijkstra(1); revdijkstra(1); db ans = 0; for (ll i=2; i <= n; i++){ if (dist1[i] >= 1e18 || distto1[i] >= 1e18) continue; for (ll j=1; j <= k; j++){ if (b[1][j] == -1 || s[i][j] == -1) continue; ll profit = s[i][j] - b[1][j]; if (profit <= 0) continue; db cur = (db)profit / (dist1[i] + distto1[i]); ans = max(ans, cur); } } cout << (ll)floor(ans); }