#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 1e3 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k, dist[maxn][maxn];
int b[maxn][maxn], s[maxn][maxn], e[maxn][maxn], g[maxn][maxn];
bool check(int eff){
memset(g, 0x3f, sizeof g);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dist[i][j] < inf) g[i][j] = eff*dist[i][j] - e[i][j];
}
}
for(int l=1;l<=n;l++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j] = min(g[i][j], g[i][l] + g[l][j]);
}
}
}
for(int i=1;i<=n;i++)
if(g[i][i] <= 0) return true;
return false;
}
int buscab(){
int ini=1, fim=int(1e9)+1, meio;
while(fim - ini > 1){
meio = (ini+fim)>>1;
if(check(meio))
ini = meio;
else
fim = meio;
}
return ini;
}
int32_t main(){
ios::sync_with_stdio(false), cin.tie(0);
memset(dist, 0x3f, sizeof dist);
memset(b, -1, sizeof b);
memset(s, -1, sizeof s);
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];
}
}
for(int i=1;i<=m;i++){
int u, v, d;
cin >> u >> v >> d;
dist[u][v] = min(dist[u][v], d);
}
for(int l=1;l<=n;l++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int l=1;l<=k;l++){
if(s[j][k] != -1 && b[i][k] != -1)
e[i][j] = max(e[i][j], s[j][k] - b[i][k]);
}
}
}
cout << buscab() << "\n";
return 0;
}
