#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
bool condition(ll n, vector<vector<ll>> lengths) {
for(ll j = 0; j < n; j++) { // inside node
for(ll i = 0; i < n; i++) {
for(ll k = 0; k < n; k++) {
lengths[i][k] = min(lengths[i][k], lengths[i][j] + lengths[j][k]);
}
}
}
bool isCorrect = false;
for(ll i = 0; i < n; i++) if(lengths[i][i] <= 0) isCorrect = true;
return isCorrect;
}
int main() {
fastIO;
ll N, M, K; cin >> N >> M >> K;
vector<vector<ll>> buy(N, vector<ll>(N, 0ll));
vector<vector<ll>> sell(N, vector<ll>(N, 0ll));
vector<vector<ll>> edges(N, vector<ll>(N, (ll)1e9));
for(int i = 0; i < N; i++) {
for(int j = 0; j < K; j++) {
cin >> buy[i][j] >> sell[i][j];
}
}
for(int i = 0; i < M; i++) {
ll a, b, w; cin >> a >> b >> w;
a--;b--;
edges[a][b] = w;
}
// initial floyd-warshall on the edges
for(int j = 0; j < N; j++) {
for(int i = 0; i < N; i++) {
for(int k = 0; k < N; k++) {
edges[i][k] = min(edges[i][k], edges[i][j] + edges[j][k]);
}
}
}
vector<vector<ll>> profit(N, vector<ll>(N, 0ll));
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
for(int k = 0; k < K; k++) {
if ((buy[i][k] != -1) && (sell[j][k] != -1)) {
profit[i][j] = max(profit[i][j], sell[j][k] - buy[i][k]);
}
}
}
}
// binary search the valid value
ll l = 0, r = 1e9 + 1;
vector<vector<ll>> actualEdges(N, vector<ll>(N, 0));
while(l + 1 < r) {
ll m = (l+r)>>1ll;
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < N; j++) {
actualEdges[i][j] = (m * min(edges[i][j], (ll)1e9)) - profit[i][j];
}
}
if (condition(N, actualEdges)) { // that means that the answer is valid
l = m;
} else {
r = m;
}
}
cout << l << '\n';
return 0;
}
