#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e2 + 5, inf = 1e9;
int s[maxn][10 * maxn], b[maxn][10 * maxn];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, k; 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];
}
vector<vector<int>> dist(n + 1, vector<int>(n + 1, inf)), at(n + 1, vector<int>(n + 1));
while(m--){
int u, v; cin >> u >> v;
cin >> dist[u][v];
}
for(int c = 1; c <= n; c++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) dist[i][j] = min(dist[i][j], dist[i][c] + dist[c][j]);
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int item = 1; item <= k; item++){
if(b[i][item] != -1 && s[j][item] != -1) at[i][j] = max(at[i][j], s[j][item] - b[i][item]);
}
}
}
int l = 0, r = inf, ans = 0;
while(l <= r){
int mid = (l + r) / 2;
vector<vector<int>> cost(n + 1, vector<int>(n + 1, -inf));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) cost[i][j] = at[i][j] - mid * dist[i][j];
}
for(int c = 1; c <= n; c++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) cost[i][j] = max(cost[i][j], cost[i][c] + cost[c][j]);
}
}
bool ok = false;
for(int i = 1; i <= n; i++) ok |= (cost[i][i] >= 0);
if(ok) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans;
}
