#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
const int INF = 2e9;
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, m, k, u, v; cin >> n >> m >> k;
int b[n][k], s[n][k], ok = 1;
for(int i=0; i<n; ++i){
for(int j=0; j<k; ++j){
cin >> b[i][j] >> s[i][j];
if(b[i][j] < 0) b[i][j] = INF;
if(s[i][j] < 0) s[i][j] = -INF;
}
}
int d[n][n], p[n][n];
for(int i=0; i<n; ++i) fill(d[i], d[i]+n, INF), fill(p[i], p[i]+n, 0LL);
while(m--) cin >> u >> v >> d[u-1][v-1];
for(int l=0; l<n; ++l)
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
d[i][j] = min(d[i][j], d[i][l] + d[l][j]);
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
for(int l=0; l<k; ++l)
p[i][j] = max(p[i][j], (b[i][l] < 0 or s[j][l] < 0) ? 0LL : s[j][l]-b[i][l]);
int low = 0, high = 1e9;
while(low < high){
int x = (low + high + 1) / 2LL;
int dp[n][n];
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
dp[i][j] = p[i][j] - x * d[i][j];
for(int l=0; l<n; ++l)
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
dp[i][j] = max(dp[i][j], dp[i][l] + dp[l][j]);
bool ok = 0;
for(int i=0; i<n; ++i)
if(dp[i][i] >= 0) ok = 1;
if(ok) low = x;
else high = x - 1;
}
cout << (ok ? low : 0LL);
}
