/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e15
#define INFll 1e15
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
#define int ll
int _n, _k;
size_t _m;
vector<vector<ll>> dist, val;
vector<vector<pair<int, int>>> adj, items;
inline void systemd() {
dist.assign(_n + 1, vector<ll>(_n + 1, INFi));
val.assign(_n + 1, vector<ll>(_n + 1, 0));
adj.assign(_n + 1, vector<pair<int, int>>(0));
items.assign(_n + 1, vector<pair<int, int>>(_k + 1));
}
char solve() {
if (!(cin >> _n >> _m >> _k))
return 1;
systemd();
for (size_t v = 1; v <= _n; v++) {
for (size_t j = 1; j <= _k; j++) {
cin >> items[v][j].first >> items[v][j].second;
}
// dist[v][v] = 0;
}
for (size_t j = 0; j < _m; j++) {
int u, v, t;
cin >> u >> v >> t;
adj[u].push_back(make_pair(v, t));
dist[u][v] = t;
}
for (int k = 1; k <= _n; k++) {
for (int v = 1; v <= _n; v++) {
for (int u = 1; u <= _n; u++) {
if (dist[v][k] == INFi || dist[k][u] == INFi)
continue;
dist[v][u] = min(dist[v][u], dist[v][k] + dist[k][u]);
}
}
}
for (int i = 1; i <= _n; i++) {
for (int j = 1; j <= _n; j++) {
for (int c = 1; c <= _k; c++) {
if (items[i][c].first != -1 && items[j][c].second != -1) {
val[i][j] = max<ll>(val[i][j], items[j][c].second - items[i][c].first);
}
}
}
}
int l = 0, r = INFi, mid, ans = 0;
while (l <= r) {
mid = (l + r) >> 1LL;
vector<vector<ll>> cost(_n + 1, vector<ll>(_n + 1, -INFi));
for (int v = 1; v <= _n; v++) {
for (int u = 1; u <= _n; u++) {
cost[v][u] = max(cost[v][u], val[v][u] - (ll)dist[v][u] * mid);
}
}
for (int k = 1; k <= _n; k++) {
for (int v = 1; v <= _n; v++) {
for (int u = 1; u <= _n; u++) {
cost[v][u] = max(cost[v][u], cost[v][k] + cost[k][u]);
}
}
}
char ok = false;
for (int v = 1; v <= _n; v++) {
ok |= (cost[v][v] >= 0);
}
if (ok) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
cout << ans << ln;
return 0;
}
// Attack on titan<3
signed main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int t = 1e9;
// cin >> t;
for (int cases = 0; cases < t; cases++) {
if (solve())
break;
#ifdef ONPC
cerr << "__________\n";
#endif
}
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
