#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
const int INF = 1e11;
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];
for(int i=0; i<n; ++i)
for(int j=0; j<k; ++j)
cin >> b[i][j] >> s[i][j];
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 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 ? 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)
for(int j=i+1; j<n; ++j)
if(dp[i][j] + dp[j][i] >= 0) ok = 1;
if(ok) low = x;
else high = x - 1;
}
cout << low nl;
}
