#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
const int INF = LLONG_MAX / 2;
inline void solve(){
int n, m, k;
cin >> n >> m >> k;
vvi dist(n + 1, vi(n + 1, INF));
vvi b(n + 1, vi(k + 1)), s(n + 1, vi(k + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
cin >> b[i][j] >> s[i][j];
}
}
for(int i = 0; i < m; i++){
int a, b, w;
cin >> a >> b >> w;
dist[a][b] = min(dist[a][b], w);
}
auto floyd_warshall = [&](vvi &dist) -> void {
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
/*cout << "dist: \n";
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cout << dist[i][j] << " ";
}
cout << "\n";
}*/
return;
};
floyd_warshall(dist);
vvi profit(n + 1, vi(n + 1));
for(int i = 1; i <= n; i++){ // find the maximum profit of each path
for(int j = 1; j <= n; j++){
for(int x = 1; x <= k; x++){
if(s[j][x] == -1 || b[i][x] == -1) continue;
profit[i][j] = max(profit[i][j], s[j][x] - b[i][x]);
}
}
}
// ratios are inconvenient, so let's consider a simpler problem: given R, can we find a profit cycle with profit P and time T such that P / T >= R
// This is convenient because we can make it linear: this problem is equivalent to checking whether we can find a profit cycle with profit P and time T such that P - TR >= 0
// If we weight each edge as p - tR, this is equivalent to checking whether a non-negative cycle exists in the graph.
// weight as tR - p (0 >= TR - P) and look for a negative cycle
// R is valid if R + 1 is valid -> binary search
auto check = [&](int r) -> bool {
vvi new_dist(n + 1, vi(n + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
new_dist[i][j] = min(dist[i][j], INF / r) * r - profit[i][j];
}
}
floyd_warshall(new_dist);
for(int i = 1; i <= n; i++){
if(new_dist[i][i] <= 0) return true;
}
return false;
};
auto bs = [&]() -> int {
int lo = 1, hi = 1e9, ret = lo, mid;
while(hi >= lo){
mid = lo + (hi - lo) / 2;
if(check(mid)){
ret = mid;
lo = mid + 1;
}
else{
hi = mid - 1;
}
}
return ret;
};
cout << bs() << "\n";
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
