#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 100 + 10;
const int MAXK = 1000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
int n, m, k;
int vis[MAXN];
bool cycleEdge[MAXN][MAXN];
llong dist[MAXN][MAXN];
llong cost[MAXN][MAXN];
llong edge[MAXN][MAXN];
llong buy[MAXN][MAXK];
llong sell[MAXN][MAXK];
llong vals[MAXN];
llong cpy[MAXN];
bool dfs(int node)
{
vis[node] = 1;
for (int i = 1 ; i <= n ; ++i)
{
if (!cycleEdge[node][i] || vis[i] == 2)
{
continue;
}
if (vis[i] == 1)
{
return true;
}
if (dfs(i))
{
return true;
}
}
vis[node] = 2;
return false;
}
bool check(llong c)
{
for (int u = 1 ; u <= n ; ++u)
{
for (int v = 1 ; v <= n ; ++v)
{
if (dist[u][v] == INF)
{
edge[u][v] = INF;
} else
{
edge[u][v] = c * dist[u][v] - cost[u][v];
}
}
}
std::fill(vals + 1, vals + 1 + n, INF);
vals[1] = 0;
for (int times = 1 ; times < n ; ++times)
{
for (int u = 1 ; u <= n ; ++u)
{
for (int v = 1 ; v <= n ; ++v)
{
if (vals[u] + edge[u][v] < vals[v])
{
vals[v] = vals[u] + edge[u][v];
}
}
}
}
for (int i = 1 ; i <= n ; ++i)
{
cpy[i] = vals[i];
}
for (int u = 1 ; u <= n ; ++u)
{
for (int v = 1 ; v <= n ; ++v)
{
if (vals[u] + edge[u][v] < vals[v])
{
vals[v] = vals[u] + edge[u][v];
}
}
}
for (int i = 1 ; i <= n ; ++i)
{
if (vals[i] != cpy[i])
{
return true;
}
}
for (int u = 1 ; u <= n ; ++u)
{
for (int v = 1 ; v <= n ; ++v)
{
cycleEdge[u][v] = (v != u && vals[v] == vals[u] + edge[u][v]);
}
}
std::fill(vis + 1, vis + 1 + n, 0);
for (int i = 1 ; i <= n ; ++i)
{
if (!vis[i] && dfs(i))
{
return true;
}
}
return false;
}
void solve()
{
for (int mid = 1 ; mid <= n ; ++mid)
{
for (int from = 1 ; from <= n ; ++from)
{
if (from == mid) continue;
for (int to = 1 ; to <= n ; ++to)
{
if (mid == to || from == to) continue;
dist[from][to] = std::min(dist[from][to], dist[from][mid] + dist[mid][to]);
}
}
}
for (int u = 1 ; u <= n ; ++u)
{
for (int v = 1 ; v <= n ; ++v)
{
cost[u][v] = 0;
for (int i = 1 ; i <= k ; ++i)
{
cost[u][v] = std::max(cost[u][v], sell[v][i] - buy[u][i]);
}
}
}
int l = 0, r = INTINF + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
std::cout << l << '\n';
}
void input()
{
std::cin >> n >> m >> k;
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= k ; ++j)
{
std::cin >> buy[i][j] >> sell[i][j];
if (buy[i][j] == -1)
{
buy[i][j] = INF;
}
if (sell[i][j] == -1)
{
sell[i][j] = 0;
}
}
}
std::fill(&dist[0][0], &dist[MAXN - 1][MAXN - 1] + 1, INF);
for (int i = 1 ; i <= m ; ++i)
{
llong u, v, d;
std::cin >> u >> v >> d;
dist[u][v] = std::min(dist[u][v], d);
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
