#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define pob pop_back
#define SZ(x) (int)(x.size())
#define all(x) begin(x), end(x)
#ifdef LOCAL
#define HEHE freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define HEHE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 7122;
#endif
using namespace std;
#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }
#define int long long
const int MAXN = 105;
int n;
void floyd(int G[MAXN][MAXN]) {
FOR (i, 1, n) FOR (j, 1, n)
FOR (k, 1, n)
chmin(G[i][j], G[i][k] + G[k][j]);
}
const int inf = (1ll << 60) - 1;
int m, k;
int G[MAXN][MAXN], profit[MAXN][MAXN];
int G2[MAXN][MAXN];
int b[MAXN][1005], s[MAXN][1005];
signed main() {
HEHE
cin >> n >> m >> k;
FOR (i, 1, n) {
FOR (j, 1, k) {
cin >> b[i][j] >> s[i][j];
}
}
FOR (i, 1, n) {
FOR (j, 1, n) {
G[i][j] = inf;
// profit[i][j] = -1e9;
}
}
FOR (i, 1, m) {
int u, v, w; cin >> u >> v >> w;
chmin(G[u][v], w);
}
floyd(G);
FOR (i, 1, n) {
FOR (j, 1, n) {
FOR (x, 1, k)
if (s[j][x] != -1 and b[i][x] != -1)
chmax(profit[i][j], s[j][x] - b[i][x]);
}
}
// profit / len >= x
// x * len - profit <= 0
int l = 0, r = 1e9 + 10;
while (l < r - 1) {
int mid = (l + r) / 2;
FOR (i, 1, n) {
FOR (j, 1, n) {
G2[i][j] = mid * min(G[i][j], inf/mid) - profit[i][j];
chmin(G2[i][j], inf);
}
}
floyd(G2);
int ok = 0;
FOR (i, 1, n) {
if (G2[i][i] <= 0) ok = 1;
}
if (ok) l = mid;
else r = mid;
}
cout << l << '\n';
}
