#include<bits/stdc++.h> using namespace std; int n , m , k; const int N = 107; const int K = 1003; typedef long long ll; ll buyData[N][K]; ll sellData[N][K]; ll cost[N][N]; bool reach[N][N]; bool mark[N]; pair<ll , ll> ans[N][N]; ll d[N][N]; vector<pair<int ,ll>> adj[N]; void getInput(){ memset(buyData , -1 , sizeof buyData); memset(sellData , -1 , sizeof sellData); cin >> n >> m >> k; for(int i = 0; i < n; i++){ for(int j = 0; j < 2 * k; j++){ int co; cin >> co; if(j % 2 == 0) buyData[i][j / 2] = co; else sellData[i][j / 2] = co; } } for(int i = 0; i < m; i++){ int u , v; ll w; cin >> u >> v >> w; u-- , v--; adj[u].push_back({v , w}); adj[v].push_back({u , w}); } } void dfs(int u , int src){ mark[u] = true; reach[src][u] = true; for(auto v: adj[u]){ if(mark[v.first]) continue; dfs(v.first , src); } } void calcRech(){ for(int i = 0; i < n; i++){ memset(mark , 0 , sizeof mark); dfs(i , i); } } void calcCost(){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(!reach[i][j]){ cost[i][j] = 1e18; cost[j][i] = 1e18; continue; } for(int f = 0; f < k; f++){ cost[i][j] = max(cost[i][j] , sellData[j][f] - buyData[i][f]); } } } } void floydDis(){ for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) d[i][j] = 1e17; for(auto v: adj[i]){ d[i][v.first] = min(d[i][v.first] , v.second); } } for(int i = 0; i < n; i++){ for(int u = 0; u < n; u++){ for(int v = 0; v < n; v++){ if(!reach[u][v]) continue; d[u][v] = min(d[u][v] , d[u][i] + d[i][v]); } } } } pair<ll ,ll> maxPair(pair<ll , ll> x , pair<ll ,ll> y){ if(x.first * y.second < x.second * y.first) return y; return x; } void floydAns(){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) { ans[i][j] = {1e18 , 1}; if(reach[i][j]) ans[i][j] = {cost[i][j] , d[i][j]}; } } for(int i = 0; i < n; i++){ for(int u = 0; u < n; u++){ for(int v = 0; v < n; v++){ if(u == v) continue; if(!reach[u][v]) continue; if(!reach[u][i] || !reach[i][v]) continue; ans[u][v] = maxPair({ans[u][i].first + ans[i][v].first , ans[u][i].second + ans[i][v].second} , ans[u][v]); } } } } ll getAns(){ pair<ll , ll> ansPair = {0 , 1}; for(int u = 0; u < n; u++){ for(int v = 0; v < n; v++){ if(u == v) continue; if(!reach[u][v] || !reach[v][u]) continue; ansPair = max(ansPair , {ans[u][v].first + ans[v][u].first , ans[u][v].second + ans[v][u].second}); } } return ansPair.first / ansPair.second; } int main(){ getInput(); calcRech(); calcCost(); floydDis(); floydAns(); cout << getAns() << endl; return 0; }