#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
ld eps = 1e-15d;
ld inf = 1e18;
int n,m,k;
int b[105][1005],s[105][1005];
int d[105][105];
int f[105][105];
ld cost[105][105];
vector<pair<int,ld>> g[105];
bool inq[105];
int nrq[105];
ld dist[105];
ld dd[105][105];
bool ciclu_negativ()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dd[i][j] = cost[i][j];
for (int i = 1; i <= n; i++)
dd[i][i] = 0;
for (int kk = 1; kk <= n; kk++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dd[i][j] = min(dd[i][j],dd[i][kk] + dd[kk][j]);
for (int i = 1; i <= n; i++)
if (dd[i][i] < 0)
return true;
return false;
}
bool pot(int t)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cost[i][j] = ((ld)f[i][j] / (ld)t) - (ld)d[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cost[i][j] = -cost[i][j] - eps;
for (int i = 1; i <= n; i++)
cost[i][i] = 0;
for (int i = 1; i <= n; i++)
{
g[i].clear();
for (int j = 1; j <= n; j++)
if (i != j)
g[i].push_back({j,cost[i][j]});
}
return ciclu_negativ();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
cin >> b[i][j] >> s[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
d[i][j] = 1e9;
for (int i = 1; i <= m; i++)
{
int x,y,cost;
cin >> x >> y >> cost;
d[x][y] = cost;
}
for (int kk = 1; kk <= n; kk++)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
d[x][y] = min(d[x][y],d[x][kk] + d[kk][y]);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
{
for (int q = 1; q <= k; q++)
{
if (b[i][q] != -1 and s[j][q] != -1)
f[i][j] = max(f[i][j],s[j][q] - b[i][q]);
}
}
}
}
int st = 0, pas = 1 << 29;
while (pas != 0)
{
if (pot(st + pas))
st += pas;
pas /= 2;
}
cout << st;
return 0;
}
/**
Fie f(i,j) = practic costul maxim pe care il fac mergand de la i la j (direct route), L(i,j) = lungimea drumului
L(i,j) calculez in n^3 cu floyd, f(i,j) in n^2k
Caut binar raspunsul, sa zicem ca incerc >= T. f(i,j) /= T, f(i,j) -= L(i,j), f(i,j) = -f(i,j), f(i,j) -= 0.0000001. Acum doar caut un ciclu negativ
Pentru asta, bellman-ford si am O(B * log), unde B este bellman ford-ul care parca era bounded by N * M deci N^3log pe worst case
**/
