#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int N = 1e2 + 5;
ll n, m, k, ans = 1e12 + 1;
vector <vector <ll>> dis, e, b, s, e1;
bool check(ll x1) {
e1 = e;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
e1[i][j] -= (x1 * dis[i][j]);
e1[i][j] *= (-1);
}
}
for(int x = 1; x <= n; x++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
e1[i][j] = min(e1[i][j], e1[i][x] + e1[x][j]);
}
}
}
for(int i = 1; i <= n; i++) {
if(e1[i][i] < 0) return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> k;
b.assign(n+1, vector <ll> (k+1, 0)), s.assign(n+1, vector <ll> (k+1, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
cin >> b[i][j] >> s[i][j];
}
}
dis.assign(n+1, vector <ll> (n+1, 1e9));
for(int i = 1; i <= m; i++) {
int u1, u2, w;
cin >> u1 >> u2 >> w;
dis[u1][u2] = 2;
}
for(int x = 1; x <= n; x++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dis[i][j] = min(dis[i][j], dis[i][x] + dis[x][j]);
}
}
}
e.assign(n+1, vector <ll> (n+1, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int x = 1; x <= k; x++) {
if(b[i][x] == -1 or s[j][x] == -1) continue;
e[i][j] = max(e[i][j], (s[j][x] - b[i][x]));
}
}
}
ll l = 0, r = 1e12;
while(l <= r) {
ll md = (l + r) / 2;
if(check(md)) {
l = md+1;
ans = md;
}
else {
r = md-1;
}
}
cout << (ans == 1e12 + 1 ? -1 : ans);
return 0;
}
