#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
const int MAXN = 105;
const int MAXP = 1005;
const llint INF = 1000000007LL;
llint n, m, p;
llint buy[MAXN][MAXP], sell[MAXN][MAXP];
llint d[MAXN][MAXN], g[MAXN][MAXN];
llint cost[MAXN][MAXN];
void ispis () {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
cout << g[i][j] << " ";
}
cout << endl;
}
}
bool moze (llint t) {
if (t == 0) return 1;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
cost[i][j] = t * d[i][j] - g[i][j];
if (d[i][j] == INF) cost[i][j] = INF * INF;
}
}
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (cost[i][k] + cost[k][j] < cost[i][j]) {
cost[i][j] = cost[i][k] + cost[k][j];
}
if (cost[i][j] < -INF*INF) cost[i][j] = -INF*INF;
}
}
}
for (int i=1; i<=n; i++) {
if (cost[i][i] <= 0) return 1;
}
return 0;
}
void precompute () {
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
llint res = 0;
for (int k=1; k<=p; k++) {
res = max(res, sell[j][k] - buy[i][k]);
}
g[i][j] = res;
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> p;
for (int i=1; i<=n; i++) {
for (int j=1; j<=p; j++) {
cin >> buy[i][j] >> sell[i][j];
if (buy[i][j] == -1) buy[i][j] = INF;
if (sell[i][j] == -1) sell[i][j] = -INF;
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
d[i][j] = INF;
}
}
for (int i=1; i<=m; i++) {
int a, b, c;
cin >> a >> b >> c;
d[a][b] = c;
}
precompute();
llint lo = 0, hi = 1000000001;
while (lo < hi) {
llint mid = (lo + hi + 1) / 2;
if (moze(mid)) {
lo = mid;
} else {
hi = mid-1;
}
}
cout << lo;
return 0;
}
