#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int INF = 1e18 + 10;
const int MAXN = 1e3 + 10;
struct Edge {
int v, u, p, t;
};
int B[MAXN][MAXN];
int S[MAXN][MAXN];
int P[MAXN][MAXN];
int dis[MAXN][MAXN];
int dist[MAXN][MAXN];
vector <Edge> edge;
bool check(int n, int mid)
{
for (auto [v, u, p, t] : edge)
dis[v][u] = (t == INF ? INF : mid * t) - p;
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
for (int i = 1; i <= n; i++)
{
if (dis[i][i] <= 0)
return true;
}
return false;
}
signed main()
{
int n, m, k, ans = 0;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
dist[i][j] = INF;
}
}
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 <= m; i++)
{
int v, u, w;
cin >> v >> u >> w;
dist[v][u] = w;
}
for (int t = 1; t <= n; t++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);
}
}
}
for (int i = 1; i <= k; i++)
{
for (int v = 1; v <= n; v++)
{
for (int u = 1; u <= n; u++)
{
if (B[v][i] == -1 || S[u][i] == -1)
continue;
P[v][u] = max(P[v][u], S[u][i] - B[v][i]);
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
edge.push_back({i, j, P[i][j], dist[i][j]});
}
}
int l = 0, r = sqrt(INF);
while (r - l > 1)
{
int mid = (l + r) >> 1;
if (check(n, mid))
l = mid;
else
r = mid;
}
cout << l << endl;
return 0;
}
