#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e3+5;
int n,m,k;
int b[N][N],s[N][N],d[N][N][2],w[N][N];
void floyd(int type){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int l = 1; l <= n; l++) d[i][j][type] = min(d[i][j][type],d[i][l][type]+d[l][j][type]);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) d[i][j][0] = 1e18;
}
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,w;
cin >> u >> v >> w;
d[u][v][0] = w;
}
floyd(0);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int l = 1; l <= k; l++){
if(b[i][l] != -1 && s[j][l] != -1) w[i][j] = max(w[i][j],s[j][l]-b[i][l]);
}
}
}
int l = 1;
int r = 1e9;
int ans;
while(l <= r){
int mid = (l+r)/2;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) d[i][j][1] = mid*min(d[i][j][0],(int)1e18/mid)-w[i][j];
}
floyd(1);
bool ck = false;
for(int i = 1; i <= n; i++){
if(d[i][i][1] <= 0){
ck = true;
break;
}
}
if(ck){
ans = mid;
l = mid+1;
}
else r = mid-1;
}
cout << ans;
}
