#include <bits/stdc++.h>
using namespace std;
pair <int , int> cost[101][1001];
pair <int , int64_t> factor[101][101];
int64_t distanta[101][101];
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int numar_noduri , numar_muchii , numar_candidati;
cin >> numar_noduri >> numar_muchii >> numar_candidati;
for (int nod = 1 ; nod <= numar_noduri ; nod++) {
for (int indice = 1 ; indice <= numar_candidati ; indice++)
{ cin >> cost[nod][indice].first >> cost[nod][indice].second; }
}
for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++) {
for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++)
{
factor[nod_1][nod_2].second = 1e18;
if (nod_1 == nod_2)
{ continue; }
for (int indice = 1 ; indice <= numar_candidati ; indice++) {
if (cost[nod_2][indice].second != -1 && cost[nod_1][indice].first != -1)
{ factor[nod_1][nod_2].first = max(factor[nod_1][nod_2].first , cost[nod_2][indice].second - cost[nod_1][indice].first); }
}
}
}
while (numar_muchii--)
{ int nod[2]; cin >> nod[0] >> nod[1] >> factor[nod[0]][nod[1]].second; }
for (int intermediar = 1 ; intermediar <= numar_noduri ; intermediar++) {
for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++) {
for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++) {
if (nod_1 != nod_2)
{ factor[nod_1][nod_2].second = min(factor[nod_1][nod_2].second , factor[nod_1][intermediar].second + factor[intermediar][nod_2].second); }
}
}
}
int stanga = 1 , dreapta = 1e9;
while (stanga <= dreapta)
{
const int mijloc = (stanga + dreapta) / 2;
for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++) {
for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++) {
if (factor[nod_1][nod_2].second != 1e18)
{ distanta[nod_1][nod_2] = factor[nod_1][nod_2].first - 1LL * mijloc * factor[nod_1][nod_2].second; }
else
{ distanta[nod_1][nod_2] = -1e18; }
}
}
for (int intermediar = 1 ; intermediar <= numar_noduri ; intermediar++) {
for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++) {
for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++) {
if (distanta[nod_1][intermediar] != -1e18 && distanta[nod_2][intermediar] != -1e18)
{ distanta[nod_1][nod_2] = max(distanta[nod_1][nod_2] , distanta[nod_1][intermediar] + distanta[intermediar][nod_2]); }
}
}
}
if (distanta[1][1] >= 0) { stanga = mijloc + 1; }
else { dreapta = mijloc - 1; }
}
cout << dreapta;
return 0;
}
