#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e2 + 5, L = 1e3 + 5, INF = 4e18;
int n, m, l, dist[N][N], dp[N][N], b[N][L], s[N][L], g[N][N];
bool ok(int x){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
if(i == j || dist[i][j] == INF) g[i][j] = -INF;
else g[i][j] = dp[i][j] - x * dist[i][j];
}
}
for(int k = 1;k<=n;k++){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
g[i][j] = max(g[i][j], g[i][k] + g[k][j]);
}
}
}
for(int i = 1;i<=n;i++) if(g[i][i] >= 0) return 1;
return 0;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> l;
for(int i = 1;i<=n;i++) for(int j = 1;j<=l;j++) cin >> b[i][j] >> s[i][j];
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) dist[i][j] = (i == j ? 0 : INF);
for(int i = 1;i<=m;i++){
int u, v, w; cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
}
for(int t = 1;t<=l;t++){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
if(b[i][t] != -1 && s[j][t] != -1) dp[i][j] = max(dp[i][j], s[j][t] - b[i][t]);
}
}
}
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]);
int l = 0, r = 1e9, ans = -1;
while(l <= r){
int md = (l + r) / 2;
if(ok(md)){
ans = md;
l = md + 1;
}else{
r = md - 1;
}
}
cout << ans;
}
