#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,m,k;
cin>>n>>m>>k;
vector<vector<ll>>b(n,vector<ll>(k)),s(n,vector<ll>(k));
for(int i = 0;i<n;i++){
for(int j = 0;j<k;j++){
cin>>b[i][j]>>s[i][j];
}
}
vector<vector<pair<ll,ll>>>gp(n);
vector<vector<ll>>d(n,vector<ll>(n,1e18));
for(int i = 0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
gp[--u].push_back({--v,w});
d[u][v]=w;
}
for(int p = 0;p<n;p++){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
d[i][j] = min(d[i][j],d[i][p]+d[p][j]);
}
}
}
vector<vector<ll>>max_delta(n,vector<ll>(n));
for(int p = 0;p<k;p++){
for(int i = 0;i<n;i++){
for(int j= 0;j<n;j++){
if(b[i][p]!=-1 && s[j][p]!=-1){
max_delta[i][j] = max(max_delta[i][j], s[j][p] - b[i][p]);
}
}
}
}
ll l = 0,r = 1e15;
while(l+1<r){
vector<vector<long long>> d1(n, vector<long long>(n, -1e18));
long long m = (l + r) / 2;
for (int i=0;i<n;++i) {
for (int j=0;j<n;++j) {
long long p=1e18/m;
d1[i][j]=max_delta[i][j]-m*min(p,d[i][j]);
}
}
for (int p=0;p<n;++p) {
for (int i=0;i<n;++i) {
for (int j=0;j<n;++j) {
d1[i][j] = max(d1[i][j], d1[i][p] + d1[p][j]);
}
}
}
bool f = 0;
for (int i = 0; i < n; ++i) if (d1[i][i] >= 0) f = 1;
d1 = vector<vector<long long>>(n, vector<long long>(n, -1e18));
if (f) l = m;
else r = m;
}
cout<<l<<endl;
}
