/**
* In the name of Allah
* We are nothing and you're everything
* author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
const char nl = '\n';
const int N = 105;
const int K = 1005;
const int inf = 1e10;
int n, m, k;
int b[N][K], s[N][K];
int g[N][N], profit[N][N], g2[N][N];
void init() {
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)g[i][j] = inf;
}
void build(int adj[N][N]) {
for (int k2 = 1; k2 <= n; ++k2)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
adj[i][j] = min(adj[i][j], adj[i][k2]+adj[k2][j]);
}
bool check(int mid) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
g2[i][j] = min(g[i][j], inf/mid)*mid-profit[i][j];
}
build(g2);
for (int i = 1; i <= n; ++i)
if (g2[i][i] <= 0)return true;
return false;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(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];
}
init();
for (int i = 0; i < m; ++i) {
int u, v, w; cin >> u >> v >> w;
g[u][v] = min(g[u][v], w);
}
build(g);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k2 = 1; k2 <= k; ++k2)
if (s[j][k2] != -1 && b[i][k2] != -1)
profit[i][j] = max(profit[i][j], s[j][k2]-b[i][k2]);
int l = 1, r = 1e9;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid))l = mid+1;
else r = mid-1;
}
cout << r;
return 0;
}
