#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
ld eps = 0.00000000001d;
int n,m,k;
int b[105][1005],s[105][1005];
int d[105][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];
bool ciclu_negativ()
{
queue<int> q;
for (int i = 1; i <= n; i++)
inq[i] = true,nrq[i] = 1,dist[i] = 0,q.push(i);
while (!q.empty())
{
int nod = q.front();
q.pop();
inq[nod] = false;
for (auto vecin : g[nod])
{
if (dist[vecin.first] > dist[nod] + vecin.second)
{
dist[vecin.first] = dist[nod] + vecin.second;
if (!inq[vecin.first])
{
inq[vecin.first] = true;
nrq[vecin.first]++;
q.push(vecin.first);
if (nrq[vecin.first] > n)
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] = (f[i][j] / (ld)t) - (ld)d[n][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++)
{
g[i].clear();
for (int j = 1; j <= n; j++)
if (i != j and d[n][i][j] != -1)
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++)
for (int ii = 0; ii <= n; ii++)
d[ii][i][j] = -1;
for (int i = 1; i <= n; i++)
d[0][i][i] = 0;
for (int i = 1; i <= m; i++)
{
int x,y,cost;
cin >> x >> y >> cost;
d[0][x][y] = cost;
}
for (int kk = 1; kk <= n; kk++)
{
for (int x = 1; x <= n; x++)
{
for (int y = 1; y <= n; y++)
{
if (x == y)
d[kk][x][y] = 0;
else
{
d[kk][x][y] = d[kk - 1][x][y];
if (d[kk - 1][x][kk] != -1 and d[kk - 1][kk][y] != -1)
if (d[kk - 1][x][kk] + d[kk - 1][kk][y] < d[kk][x][y] or d[kk][x][y] == -1)
d[kk][x][y] = d[kk - 1][x][kk] + d[kk - 1][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
**/
