#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n'
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
#define int long long
const int MAXN = 1e2+1, MAXK = 1e3+1;
int n,m,K;
int b[MAXN][MAXK], s[MAXN][MAXK];
int dist[MAXN][MAXN], d[MAXN][MAXN], prof[MAXN][MAXN];
bool good[MAXN];
vector<pair<int,PII>> v[MAXN];
bool check(int val) {
FOR(i,1,n+1) {
FOR(j,1,n+1) {
d[i][j] = LLINF;
}
//d[i][i] = good[i] = 0;
}
FOR(i,1,n+1) {
FOR(j,1,n+1) {
if (dist[i][j] == LLINF) continue;
//if (i == j || dist[i][j] == LLINF) continue;
d[i][j] = dist[i][j]*val-prof[i][j];
}
}
FOR(k,1,n+1) {
FOR(i,1,n+1) {
FOR(j,1,n+1) {
if (d[i][k]+d[k][j] == 0 && i == j && j != k) good[i] = 1;
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}
}
}
// FOR(i,1,n+1) {
// FOR(j,1,n+1) cout << d[i][j] << ' ';
// cout << ln;
// }
// cout << ln;
FOR(i,1,n+1) if (d[i][i] <= 0) return 1;
return 0;
}
signed main() {
OPTM;
cin >> n >> m >> K;
FOR(i,1,n+1) {
FOR(j,1,K+1) cin >> b[i][j] >> s[i][j];
}
FOR(i,1,n+1) {
FOR(j,1,n+1) {
dist[i][j] = LLINF;
}
//dist[i][i] = 0;
}
FOR(i,0,m) {
int x,y,w; cin >> x >> y >> w;
int mx = 0;
FOR(j,1,K+1)
v[x].PB({y,{mx,w}});
dist[x][y] = w;
}
FOR(k,1,n+1) {
FOR(i,1,n+1) {
FOR(j,1,n+1) {
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
}
}
}
FOR(i,1,n+1) {
FOR(j,1,n+1) {
FOR(x,1,K+1) {
if (dist[i][j] == LLINF) continue;
if (s[j][x] != -1 && b[i][x] != -1) prof[i][j] = max(prof[i][j], s[j][x]-b[i][x]);
}
}
}
int l = 1, r = 1LL*(1e9+1);
while (l < r) {
int mid = (l+r)/2;
if (check(mid)) l = mid+1;
else r = mid;
}
cout << l-1;
}
