#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 105;
const int MAX_K = 1005;
const long long llINF = 1e18 + 7;
long long B[MAX_N][MAX_K], S[MAX_N][MAX_K];
long long dist[MAX_N][MAX_N], dist2[MAX_N][MAX_N];
long long profit[MAX_N][MAX_N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, M, K;
cin >> N >> M >> K;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
dist[i][j] = llINF;
}
}
for(int i = 1; i <= N; i++) {
for(int k = 1; k <= K; k++) {
cin >> B[i][k] >> S[i][k];
}
}
while(M--) {
int v, w, t;
cin >> v >> w >> t;
dist[v][w] = t;
}
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 i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
for(int k = 1; k <= K; k++) {
if(B[i][k] != -1 and S[j][k] != -1) {
profit[i][j] = max(profit[i][j], S[j][k] - B[i][k]);
}
}
}
}
int l = 1, r = 1e9, ans = 0;
while(l <= r) {
int mid = (l + r) / 2;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
dist2[i][j] = llINF;
if(dist[i][j] != llINF) {
dist2[i][j] = dist[i][j] * mid - profit[i][j];
}
}
}
for(int k = 1; k <= N; k++) {
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
dist2[i][j] = min(dist2[i][j], dist2[i][k] + dist2[k][j]);
}
}
}
bool hasNegCycle = false;
for(int i = 1; i <= N; i++) {
if(dist2[i][i] <= 0) {
hasNegCycle = true;
}
}
if(hasNegCycle == true) {
l = mid + 1;
ans = mid;
}
else {
r = mid - 1;
}
}
cout << ans;
return 0;
}
