#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
ll n;
vector<vector<ll>> cst, prf;
bool can(ll ans) {
vector<vector<ll>> gp(n, vector<ll>(n));
for (ll u = 0; u < n; u++) {
for (ll v = 0; v < n; v++) {
gp[u][v] = prf[u][v] - cst[u][v] * ans;
}
}
for (ll k = 0; k < n; k++) {
for (ll u = 0; u < n; u++) {
for (ll v = 0; v < n; v++) {
gp[u][v] = max(gp[u][v], gp[u][k] + gp[k][v]);
}
}
}
ll mx = -1e18;
for (ll u = 0; u < n; u++) {
for (ll v = 0; v < n; v++) {
if (u == v) continue;
mx = max(mx, gp[u][v] + gp[v][u]);
}
}
return mx >= 0;
}
void solve() {
ll m, k;
cin >> n >> m >> k;
vector<vector<ll>> b(n), s(n);
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < k; j++) {
ll x, y;
cin >> x >> y;
b[i].push_back(x);
s[i].push_back(y);
}
}
cst = vector<vector<ll>>(n, vector<ll>(n, 1e18));
for (ll i = 0; i < m; i++) {
ll u, v, t;
cin >> u >> v >> t;
u--, v--;
cst[u][v] = t;
}
for (ll u = 0; u < n; u++) cst[u][u] = 0;
for (ll k = 0; k < n; k++) {
for (ll u = 0; u < n; u++) {
for (ll v = 0; v < n; v++) {
cst[u][v] = min(cst[u][v], cst[u][k] + cst[k][v]);
}
}
}
prf = vector<vector<ll>>(n, vector<ll>(n, 0));
for (ll u = 0; u < n; u++) {
for (ll v = 0; v < n; v++) {
for (ll i = 0; i < k; i++) {
if (s[v][i] == -1 || b[u][i] == -1) continue;
prf[u][v] = max(prf[u][v], s[v][i] - b[u][i]);
}
}
}
ll l = -1, r = 1e9;
while (l + 1 < r) {
ll m = (l + r) / 2;
if (can(m)) l = m;
else r = m;
}
cout << l << endl;
}
int main() {
int t = 1;
//cin >> t;
while (t--)
solve();
}
