#define kumi_kumi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
inline void debugMode() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
const int N = 105, K = 1005;
int n, m, k;
int b[N][K], c[N][K], v[N][N];
long long t[N][N], d[N][N];
int main () {
kumi_kumi;
//debugMode();
cin >> n >> m >> k;
for(int i = 0; i < n; i++) {
for(int j = 0; j < k; j++)
cin >> b[i][j] >> c[i][j];
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
t[i][j] = 1e18;
t[i][i] = 0;
}
for(int i = 0; i < m; i++) {
int v1, w1, t1;
cin >> v1 >> w1 >> t1;
t[v1 - 1][w1 - 1] = t1;
}
for(int x = 0; x < n; x++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
t[i][j] = min(t[i][j], t[i][x] + t[x][j]);
for(int j = 0; j < k; j++) {
if(c[i][j] != -1 && b[x][j] != -1)
v[x][i] = max(v[x][i], c[i][j] - b[x][j]);
}
}
}
int l = 0, r = 1e9;
while(l + 1 < r) {
int md = (l + r) >> 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(t[i][j] > 1e17)
d[i][j] = -1e18;
else
d[i][j] = v[i][j] - t[i][j] * md;
}
d[i][i] = -1e18;
}
for(int x = 0; x < n; x++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
d[i][j] = max(d[i][j], d[i][x] + d[x][j]);
}
}
bool g = 0;
for(int i = 0; i < n; i++)
g |= (d[i][i] >= 0);
if(g)
l = md;
else
r = md;
}
cout << l;
}
