#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define ii pair<int,int>
const int N = 105;
const int K = 1010;
const int INF = LLONG_MAX / 2;
int buy[N][K];
int sell[N][K];
int n, m, k;
int dis[N][N];
int profit[N][N];
int ngraph[N][N];
signed main(){
cin >> n >> m >> k;
for(int i=1; i<=n; ++i){
for(int j=1; j<=k; ++j){
cin >> buy[i][j] >> sell[i][j];
}
}
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
dis[i][j] = INF;
}
}
for(int i=1; i<=m; ++i){
int u, v, w;
cin >> u >> v >> w;
// u--, v--;
dis[u][v] = min(dis[u][v], w);
}
for(int u=1; u<=n; ++u){
for(int v=1; v<=n; ++v){
for(int p=1; p<=n; ++p){
dis[v][p] = min(dis[v][p], dis[v][u] + dis[u][p]);
}
}
}
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
for(int l=1; l<=k; ++l){
if(sell[j][l] != -1 && buy[i][l] != -1){
profit[i][j] = max(profit[i][j], sell[j][l] - buy[i][l]);
}
}
}
}
int ans = -1;
int low = 1, high = 1e9;
while(low <= high){
int mid = low + (high - low) / 2;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
ngraph[i][j] = mid * min(INF / mid, dis[i][j]) - profit[i][j];
}
}
for(int u=1; u<=n; ++u){
for(int v=1; v<=n; ++v){
for(int p=1; p<=n; ++p){
ngraph[v][p] = min(ngraph[v][p], ngraph[v][u] + ngraph[u][p]);
}
}
}
bool ok = 0;
for(int i=1; i<=n; ++i){
if(ngraph[i][i] <= 0){
ok = 1;
}
}
if(ok){
low = mid+1;
ans = mid;
} else {
high = mid-1;
}
}
cout << ans << endl;
}
