#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
#define BIT(x, i) (((x) >> (i)) & 1)
//#define endl '\n'
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937 rng(58);
typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 100;
void solve(){
int n, m, items;
cin >> n >> m >> items;
vector<vector<int>> B(N, vector<int>(items, -1));
vector<vector<int>> S(N, vector<int>(items, -1));
const long long INF = 1e18;
vector<vector<ll>> dist(n, vector<ll>(n, INF));
for (int i = 0; i < n; i++){
for (int j = 0; j < items; j++) cin >> B[i][j] >> S[i][j];
dist[i][i] = 0;
}
while (m--){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
dist[u][v] = w;
}
for (int k = 0; k < n; k++){
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
vector<vector<int>> max_diff(n, vector<int>(n, 0));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
for (int k = 0; k < items; k++){
if (B[i][k] == -1 || S[j][k] == -1) continue;
max_diff[i][j] = max(max_diff[i][j], S[j][k] - B[i][k]);
}
}
}
function<bool(ll)> check = [&](ll val) -> bool{
for (int where = 0; where < n; where++){
vector<ll> d(n, -INF);
d[where] = 0;
vector<bool> processed(n, false);
for (int it = 0; it < n; it++){
int v = -1;
for (int i = 0; i < n; i++){
if (processed[i]) continue;
if (v == -1 || d[i] > d[v]) v = i;
}
processed[v] = true;
for (int u = 0; u < n; u++){
if (dist[v][u] != INF) d[u] = max(d[u], d[v] + max_diff[v][u] - val * dist[v][u]);
}
}
for (int v = 0; v < n; v++){
if (dist[v][where] == INF || v == where) continue;
ll cur = d[v] + max_diff[v][where] - val * dist[v][where];
if (cur >= 0) return true;
}
}
return false;
};
ll l = 1, r = 1e9;
while (l <= r){
ll mid = (l + r) >> 1;
if (check(mid)){
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << l - 1 << endl;
}
int main(){
clock_t startTime = clock();
ios_base::sync_with_stdio(false);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int test_cases = 1;
// cin >> test_cases;
for (int test = 1; test <= test_cases; test++){
// cout << (solve() ? "YES" : "NO") << endl;
solve();
}
#ifdef LOCAL
cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif
return 0;
}
