#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>
#define MAX 100
#define INF (1ll<<60)
lli n,m,k,res,a,b,c,prod;
lli dis[MAX+2][MAX+2],profit[MAX+2][MAX+2],otro[MAX+2][MAX+2];
lli compras[MAX+2][1002],ventas[MAX+2][1002];
void floyd_warshall(lli g[MAX+2][MAX+2]) {
rep(i,1,n)
rep(j,1,n)
rep(k,1,n)
g[j][k] = min(g[j][k], g[j][i]+g[i][k]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> prod;
rep(i,1,n) {
rep(j,1,n) dis[i][j] = INF;
rep(j,1,prod) cin >> compras[i][j] >> ventas[i][j];
}
rep(i,1,m) {
cin >> a >> b >> c;
dis[a][b] = c;
}
floyd_warshall(dis); //si se pasa por referencia
//defino el arreglo de profits con otro floyd_warshall
rep(i,1,n)
rep(j,1,n)
rep(k,1,prod) {
if(compras[i][k] == -1 || ventas[j][k] == -1) continue;
profit[i][j] = max(profit[i][j], ventas[j][k] - compras[i][k]);
}
lli mitad,ini = 1;
lli fin = (1ll<<30);
while (ini <= fin) {
mitad = (ini+fin)/2;
rep(i,1,n)
rep(j,1,n)
otro[i][j] = mitad * min(dis[i][j], INF/mitad) - profit[i][j];
floyd_warshall(otro);
bool ciclo_neg = false;
rep(i,1,n) if(otro[i][i] <= 0) ciclo_neg = true;
if (ciclo_neg) {
ini = mitad + 1;
res = mitad;
}
else fin = mitad-1;
}
cout << res;
return 0;
}
//checar lo de pasar el arreglo por referencia
