#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include <debug.h>
#else
#define debug(...)
#endif
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 31;
void _() {
int n, m, k;
cin >> n >> m >> k;
vector <vector <int>> b(n+1, vector <int>(k, -1)), s(n+1, vector <int>(k, -1));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < k; j++) cin >> b[i][j] >> s[i][j];
}
vector <vector <int>> dis(n+1, vector <int>(n+1, INF));
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
dis[a][b] = c;
}
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
for (int c = 1; c <= n; c++) {
dis[b][c] = min(dis[b][c], dis[b][a] + dis[a][c]);
}
}
}
vector <vector <int>> p(n+1, vector <int>(n+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int z = 0; z < k; z++) {
if (s[j][z] == -1 || b[i][z] == -1) continue;
p[i][j] = max(p[i][j], s[j][z] - b[i][z]);
}
}
}
int l = 0, r = INF, res=0;
while (l <= r) {
int mid = (l + r) / 2;
vector <vector <int>> w(n+1, vector <int>(n+1, INF));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dis[i][j] >= INF) w[i][j] = INF;
else w[i][j] = mid * dis[i][j] - p[i][j];
}
}
for (int z = 1; z <= n; z++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = min(w[i][j], w[i][z] + w[z][j]);
}
}
}
bool ok = 0;
for (int i = 1; i <= n; i++) {
if (w[i][i] <= 0) ok = 1;
}
if (ok) res = mid, l = mid + 1;
else r = mid - 1;
}
cout << res;
}
signed main() {
GOOD_LUCK
int tests=1;
// cin >> tests;
for (int i=1; i <= tests; i++) {
_();
cout << endl;
}
return 0;
}
