#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
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 = 3000 + 10;
const ll MAXK = 1000 + 10;
const ll INF = 1e9 + 10; // ?
ll n, m, tk, B[MAXN][MAXK], S[MAXN][MAXK], max_prof[MAXN][MAXN], tdist[MAXN][MAXN];
int dist[MAXN][MAXN];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for (int i = 0; i < MAXN; i++) {
memset(dist[i], 63, sizeof dist[i]);
dist[i][i] = 0;
}
cin >> n >> m >> tk;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= tk; 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], 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 <= tk; 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]);
}
}
ll l = 0, r = ll(2e9) + 10;
while (l < r) {
ll mid = (l + r + 1) >> 1;
bool flag = false;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
tdist[i][j] = dist[i][j] * mid - max_prof[i][j];
for (int k = 1; k <= n; k++)
for (int v = 1; v <= n; v++)
for (int u = 1; u <= m; u++)
if (u != v)
tdist[v][u] = min(tdist[v][u], tdist[v][k] + tdist[k][u]);
// loops
for (int v = 1; v <= n; v++)
for (int u = 1; u <= n; u++)
if (v != u)
flag |= (tdist[v][u] + tdist[u][v] <= 0);
if (flag) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}
