#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";
const long long mod = 1e9 + 7;
int n, m, k, b[105][1005], s[105][1005];
int g[105][105], ng[105][105], nng[105][105];
int L, R, ans;
void solve () {
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];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
g[i][j] = 1e9;
}
}
for(int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
g[u][v] = w;
}
for(int rep = 0; rep < 2; rep++) {
for(int l = 1; l <= n; l++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
g[i][j] = min(g[i][j], g[i][l] + g[l][j]);
}
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
int maxProfit = 0;
for(int l = 1; l <= k; l++) {
if(b[i][l] != -1 && s[j][l] != -1) {
maxProfit = max(maxProfit, s[j][l] - b[i][l]);
}
}
if(maxProfit > 0) {
ng[i][j] = maxProfit;
}
}
}
L = 1, R = 1e9, ans = 0;
while(L <= R) {
int mid = (L + R) / 2;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
nng[i][j] = -1e18;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
nng[i][j] = ng[i][j] - g[i][j] * mid;
}
}
for(int rep = 0; rep < 2; rep++) {
for(int l = 1; l <= n; l++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
nng[i][j] = max(nng[i][j], nng[i][l] + nng[l][j]);
}
}
}
}
bool possible = false;
for(int i = 1; i <= n; i++)
if(nng[i][i] >= 0) {possible = true; break;}
if(possible)
ans = mid, L = mid + 1;
else R = mid - 1;
}
cout << ans << "\n";
}
signed main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve ();
}
