#include<bits/stdc++.h>
#define int long long
using namespace std;
const int oo = 1e18;
int dis[1005][1005], buy[105][1005], sell[105][1005];
int max_option[1005][1005], cost[1005][1005];
bool check(int n, int x)
{
//Calculate cost
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(dis[i][j] >= oo) cost[i][j] = oo;
else cost[i][j] = x*dis[i][j] - max_option[i][j];
}
cost[i][i] = 1;
}
//Another floyd
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) if(cost[i][k] < oo && cost[k][j] < oo){
cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
cost[i][j] = max(cost[i][j], -oo); //Beware of overflow
}
}
}
//Check if there is a non-positive cycle
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) if(cost[i][j] + cost[j][i] <= 0) return 1;
}
return 0;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, p; cin>>n>>m>>p;
memset(dis, 0x3f, sizeof(dis));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= p; j++) cin>>buy[i][j]>>sell[i][j];
}
for(int i = 1; i <= n; i++) dis[i][i] = 0;
for(int i = 1; i <= m; i++){
int u, v, c; cin>>u>>v>>c;
dis[u][v] = min(dis[u][v], c);
}
//Precalc max option
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= p; k++) if(buy[i][k] > -1 && sell[j][k] > -1) max_option[i][j] = max(max_option[i][j], sell[j][k] - buy[i][k]);
}
}
//Floyd
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
//
int l = 1, r = 1e9, ans = 0;
while(l <= r){
int mid = (l+r)/2;
if(check(n, mid) == 1){ans = mid; l = mid+1;}
else r = mid-1;
}
cout<<ans;
}
