#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ar array
#define eb emplace_back
#define mp make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 105, maxk = 1005, inf = 1e9;
int N, M, K;
int dist[maxn][maxn], op[maxn][maxn];
int buy[maxk][maxn], sell[maxk][maxn];
ll go[maxn][maxn];
bool check(int lim) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
go[i][j] = -inf;
if (dist[i][j] == inf)
continue;
go[i][j] = op[i][j] - (ll)lim * dist[i][j];
}
}
for (int k = 1; k <= N; ++k) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
go[i][j] = max(go[i][j], go[i][k] + go[k][j]);
if (go[i][j] >= inf)
go[i][j] = inf;
}
}
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
if (go[i][j] + go[j][i] >= 0)
return true;
}
}
return false;
}
signed main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
#endif // LOCAL
cin >> N >> M >> K;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
dist[i][j] = inf;
}
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= K; ++j) {
cin >> buy[j][i] >> sell[j][i];
}
}
while (M--) {
int u, v, w; cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
}
for (int k = 1; k <= N; ++k) {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
for (int u = 1; u <= N; ++u) {
for (int v = 1; v <= N; ++v) {
for (int item = 1; item <= K; ++item) {
if (buy[item][u] != -1 && sell[item][v] != -1) {
op[u][v] = max(op[u][v], -buy[item][u] + sell[item][v]);
}
}
}
}
int lo = 1, hi = 1e9, mid;
while (lo <= hi) {
mid = (lo + hi) / 2;
if (check(mid)) lo = mid + 1;
else hi = mid - 1;
}
cout << hi;
}
