#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 100 + 10;
const ll MAXK = 1000 + 10;
const ll INF = 1e18; // ?
ll n, m, k, B[MAXN][MAXK], S[MAXN][MAXK], dist[MAXN][MAXN], max_prof[MAXN][MAXN], tdist[MAXN][MAXN];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for (int i = 0; i < MAXN; i++) {
fill(dist[i], dist[i] + MAXN, INF);
dist[i][i] = 0;
}
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 <= m; i++) {
int u, v, d;
cin >> u >> v >> d;
dist[u][v] = min(dist[u][v], 1ll * d);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int t = 1; t <= k; t++)
if (S[j][t] >= 0 && B[i][t] >= 0)
max_prof[i][j] = max(max_prof[i][j], S[j][t] - B[i][t]);
if (dist[i][j] == INF) max_prof[i][j] = 0;
}
}
ll l = 0, r = ll(1e9) + 10;
while (l < r) {
ll mid = (l + r + 1) >> 1;
bool flag = false;
memset(tdist, 63, sizeof tdist); //
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] <= (tdist[i][j] - max_prof[i][j]) / mid) //
tdist[i][j] = min(tdist[i][j], dist[i][j] * mid - max_prof[i][j]); //
// cerr << tdist[i][j] << sep;
}
//cerr << endl;
tdist[i][i] = 1;
}
for (int k = 1; k <= n; k++)
for (int v = 1; v <= n; v++)
for (int u = 1; u <= m; u++)
tdist[v][u] = min(tdist[v][u], tdist[v][k] + tdist[k][u]);
// loops
for (int v = 1; v <= n; v++)
flag |= (tdist[v][v] <= 0);
if (flag) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}
