// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
const int MAXN = 102;
const int MAXK = 1003;
const i64 INF = LLONG_MAX/2;
int N, M, K;
i64 d[MAXN][MAXN], buy[MAXN][MAXK], sell[MAXN][MAXK], p[MAXN][MAXN], f[MAXN][MAXN];
void floyd(i64 g[MAXN][MAXN]) {
for (int k = 1; k <= N; k ++) {
for (int u = 1; u <= N; u ++) {
for (int v = 1; v <= N; v ++) {
g[u][v] = min(g[u][v], g[u][k] + g[k][v]);
}
}
}
}
void Solve(void) {
cin >> N >> M >> K;
for (int i = 1; i <= N; i ++) {
for (int j = 1; j <= K; j ++) {
cin >> buy[i][j] >> sell[i][j];
}
}
for (int u = 1; u <= N; u ++) {
for (int v = 1; v <= N; v ++) {
p[u][v] = 0;
d[u][v] = INF;
}
}
for (int i = 1; i <= M; i ++) {
int u, v; i64 w; cin >> u >> v >> w;
d[u][v] = min(d[u][v], w);
}
floyd(d);
for (int u = 1; u <= N; u ++) {
for (int v = 1; v <= N; v ++) {
for (int k = 1; k <= K; k ++) {
if (sell[v][k] != -1 && buy[u][k] != -1) {
p[u][v] = max(p[u][v], sell[v][k] - buy[u][k]);
}
}
}
}
// check if there is a non-negative cycle
auto check = [&](i64 rat) {
for (int u = 1; u <= N; u ++) {
for (int v = 1; v <= N; v ++) {
// Reverse to find non-positve cycle
f[u][v] = rat * min(INF/rat, d[u][v]) - p[u][v];
}
}
floyd(f);
for (int i = 1; i <= N; i ++) if (f[i][i] <= 0) return true;
return false;
};
i64 l = 1, h = 1e18;
while (l <= h) {
i64 mid = (l + h)/2;
if (check(mid)) l = mid + 1;
else h = mid - 1;
}
cout << h << "\n";
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(10);
int Tests = 1; // cin >> Tests;
while (Tests --) {
Solve();
}
}
