#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, k, x, y, z;
cin >> n >> m >> k;
int b[n][k], s[n][k], w[n][n], p[n][n];
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) w[i][j] = INF;
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 < m; i++) {
cin >> x >> y >> z;
x--; y--;
w[x][y] = z;
}
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
}
}
}
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
p[i][j] = 0;
for(int it = 0; it < k; it++) if(s[j][it] != -1 && b[i][it] != -1) {
p[i][j] = max(p[i][j], s[j][it] - b[i][it]);
}
}
int l = 0, r = INF, md;
while(l < r) {
md = (l+r)/2;
int dist[n][n];
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
dist[i][j] = w[i][j]*md - p[i][j];
}
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
bool ok = false;
for(int i = 0; i < n; i++) if(dist[i][i] <= 0) ok = true;
if(ok) l = md+1;
else r = md;
}
cout << l-1 << '\n';
}
