#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;
int n, m, k, b[105][1005], s[105][1005], profit[105][105], dist[105][105], d[105][105];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> m >> k;
FOR (i, 1, n){
FOR (j, 1, k) cin >> b[i][j] >> s[i][j];
}
FOR (i, 1, n) FOR (j, 1, n) dist[i][j] = 1e18;
FOR (i, 1, m){
int u, v, w; cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
}
FOR (i, 1, n){
FOR (j, 1, n){
FOR (z, 1, k){
if (b[i][z] == -1 || s[j][z] == -1) continue;
profit[i][j] = max(profit[i][j], s[j][z] - b[i][z]);
}
}
}
FOR (k, 1, n) FOR (i, 1, n) FOR (j, 1, n){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int l = 1, r = 1e9, ans = 0;
while (l <= r){
int m = (l + r)/2;
FOR (i, 1, n) FOR (j, 1, n){
if (dist[i][j] == 1e18){
d[i][j] = -1e18;
} else d[i][j] = profit[i][j] - m * dist[i][j];
}
FOR (k, 1, n) FOR (i, 1, n) FOR (j, 1, n) d[i][j] = max(d[i][j], d[i][k] + d[k][j]);
bool ok = 0;
FOR (i, 1, n) ok |= (d[i][i] >= 0);
if (ok){
ans = m;
l = m + 1;
} else r = m - 1;
}
cout << ans;
return 0;
}
