#include <bits/stdc++.h>
using namespace std;
pair <int , int> cost[101][1001];
pair <int64_t , int64_t> factor[101][101];
int64_t distanta[101];
inline void Solve ()
{
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 = 1e12;
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 , (int64_t)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++)
{ factor[nod_1][nod_2].second = min(factor[nod_1][nod_2].second , factor[nod_1][intermediar].second + factor[intermediar][nod_2].second); }
}
}
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 == 1e12)
{ factor[nod_1][nod_2].first = 0; }
if (nod_1 == nod_2)
{ factor[nod_1][nod_2].first = 0; factor[nod_1][nod_2].second = 1e12; }
}
}
int64_t stanga = 1 , dreapta = 1e12;
while (stanga <= dreapta)
{
const int64_t mijloc = (stanga + dreapta) >> 1;
vector < pair < pair <int , int> , int64_t > > muchii;
for (int nod_1 = 1 ; nod_1 <= numar_noduri ; nod_1++)
{
distanta[nod_1] = -1e12;
for (int nod_2 = 1 ; nod_2 <= numar_noduri ; nod_2++) {
if (factor[nod_1][nod_2].second != 1e12)
{ muchii.emplace_back(make_pair(nod_1 , nod_2) , factor[nod_1][nod_2].first - 1LL * mijloc * factor[nod_1][nod_2].second); }
}
}
distanta[1] = 0;
for (int ramas = numar_noduri - 1 ; ramas ; ramas--) {
for (auto& muchie : muchii)
{ distanta[muchie.first.second] = max(distanta[muchie.first.second] , distanta[muchie.first.first] + muchie.second); }
}
bool gasit = false;
for (auto& muchie : muchii) {
if (muchie.first.second == 1 && distanta[muchie.first.first] + muchie.second >= 0)
{ gasit = true; break; }
}
if (gasit) { stanga = mijloc + 1; }
else { dreapta = mijloc - 1; }
}
cout << dreapta;
}
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int numar_teste = 1;
// cin >> numar_teste;
while (numar_teste--)
{ Solve(); }
return 0;
}
