#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;
const ll inf = 1e18 + 5;
const int maxn = 105, maxk = 1005;
int n, m, k;
void floyd_warshall(vector<vector<ll> >& d)
{
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++)
d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
vector<vector<ll> > d(maxn, vector<ll>(maxn, inf)), z(maxn, vector<ll>(maxn, 0));
vector<vector<ll> > b(maxn, vector<ll>(maxk)), s(maxn, vector<ll>(maxk));
bool check(ll X) // true ak existuje dobry cyklus (mozeme hladat vyssie)
{
vector<vector<ll> > dist(n, vector<ll>(n, inf));
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (d[i][j] != inf)
dist[i][j] = X * d[i][j] - z[i][j];
floyd_warshall(dist);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
if (i != j && dist[i][j] + dist[j][i] <= 0) return true;
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < n; i++) for (int j = 0; j < k; j++)
cin >> b[i][j] >> s[i][j];
for (int i = 0; i < n; i++) d[i][i] = 0;
for (int i = 0, u, v, t; i < m; i++)
cin >> u >> v >> t, d[--u][--v] = t;
floyd_warshall(d);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j && d[i][j] != inf)
for (int ki = 0; ki < k; ki++) if (b[i][ki] != -1 && s[j][ki] != -1)
z[i][j] = max(z[i][j], s[j][ki] - b[i][ki]);
ll lo = 0, hi = 1e9 + 5;
while (lo < hi)
{
ll mi = (lo + hi + 1) >> 1;
if (check(mi)) lo = mi;
else hi = mi - 1;
}
cout << lo << "\n";
return 0;
}
