#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100;
const int MAXK = 1000;
pair<ll, ll> path[MAXN][MAXN][MAXN+1];
ll buy[MAXN][MAXK], sell[MAXN][MAXK];
ll dist[MAXN][MAXN];
vector<pair<int, ll>> adj[MAXN];
double val(pair<ll, ll> p) {
// cout << "divisão" << p.first << ' ' << p.second << endl;
return (double)p.first / (double)p.second;
}
void Dijkstra(int src) {
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, src});
dist[src][src] = 0;
while (!pq.empty()) {
int v = pq.top().second; ll d = pq.top().first;
pq.pop();
if (dist[src][v] < d) continue;
for (auto [viz, w] : adj[v]) {
if (d + w >= dist[src][viz]) continue;
dist[src][viz] = d + w;
pq.push({dist[src][viz], viz});
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m, k; cin >> n >> m >> k;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
dist[i][j] = 1e18;
}
}
for (int i=0; i<n; i++) {
for (int p=0; p<k; p++) {
cin >> buy[i][p] >> sell[i][p];
}
}
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});
}
for (int i=0; i<n; i++) Dijkstra(i);
for (int u=0; u<n; u++) {
for (int v=0; v<n; v++) {
// cout << dist[u][v] << ' ';
ll mx_profit = 0;
for (int p=0; p<k; p++) {
if (buy[u][p] == -1 or sell[v][p] == -1) continue;
mx_profit = max(mx_profit, sell[v][p]-buy[u][p]);
}
// cout << u << '>' << v << ':' << mx_profit << ' ' << dist[u][v] << endl;
path[u][v][0] = {mx_profit, dist[u][v]};
if (u == v) {
path[u][v][0] = {0, 1e18};
}
}
// cout << endl;
}
for (int i=0; i<=n; i++) {
for (int mid=1; mid<=n; mid++) {
for (int u=0; u<n; u++) {
for (int v=0; v<n; v++) {
path[u][v][mid] = path[u][v][mid-1];
if (path[u][mid-1][mid-1].second == (ll)1e18 or path[mid-1][v][mid-1].second == (ll)1e18) {
// cout << "skipa" << u << ' ' << mid-1 << ' ' << v << endl;
continue;
}
pair<ll, ll> new_path = {
path[u][mid-1][mid-1].first + path[mid-1][v][mid-1].first,
path[u][mid-1][mid-1].second + path[mid-1][v][mid-1].second
};
if (val(new_path) > val(path[u][v][mid])) {
path[u][v][mid] = new_path;
}
if (mid == n) path[u][v][0] = path[u][v][n];
}
}
}
}
ll ans = 0;
for (int i=0; i<n; i++) {
// if (path[i][i][n].first / path[i][i][n].second > ans) {
// cout << "ciclo em i=" << i << ':' << path[i][i][n].first << ' ' << path[i][i][n].second << endl;
// }
ans = max(ans, path[i][i][n].first / path[i][i][n].second);
}
cout << ans << '\n';
return 0;
}
