#include "bits/stdc++.h"
using namespace std;
#define Mucho LLONG_MAX / 2
long long N, M, K;
vector< vector<long long> > Compra, Venta, Grafo1, Ganancia, Grafo2;
void Floyd_Warshall(vector< vector<long long> > &Grafo){
for(long long i = 0; i < N; i++) for(long long j = 0; j < N; j++) for(long long k = 0; k < N; k++) Grafo[j][k] = min(Grafo[j][k], Grafo[j][i] + Grafo[i][k]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>N>>M>>K;
vector<long long> a(101, Mucho);
vector<long long> b(1001, Mucho);
vector<long long> c(101, 0);
Grafo1.assign(101, a);
Grafo2.assign(101, a);
Compra.assign(101, b);
Venta.assign(101, b);
Ganancia.assign(101, c);
for(long long i = 0; i < N; i++) for(long long j = 0; j < K; j++) cin>>Compra[i][j]>>Venta[i][j];
for(long long i = 0; i < M; i++){
long long V, W, T;
cin>>V>>W>>T;
Grafo1[V - 1][W - 1] = T;
}
Floyd_Warshall(Grafo1);
for(long long i = 0; i < N; i++) for(long long j = 0; j < N; j++) for(long long k = 0; k < K; k++) if(Venta[j][k] != -1 and Compra[i][k] != -1) Ganancia[i][j] = max(Ganancia[i][j], Venta[j][k] - Compra[i][k]);
long long Inicio = 0;
long long Final = 1e9;
while(Inicio <= Final){
long long Promedio = (Inicio + Final) / 2;
for(long long i = 0; i < N; i++) for(long long j = 0; j < N; j++) Grafo2[i][j] = Promedio * min(Grafo1[i][j], Mucho / Promedio) - Ganancia[i][j];
Floyd_Warshall(Grafo2);
bool Ciclo_positivo = 0;
for(long long i = 0; i < N; i++) if(Grafo2[i][i] <= 0) Ciclo_positivo = 1;
if(Ciclo_positivo) Inicio = Promedio + 1;
else Final = Promedio - 1;
}
cout<<Final;
return 0;
}
