#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
ll n, m, k, l, r=1e9+7, mid,a,bb,c;
vector<pii> adj[105];
ll b[105][1005], s[105][1005];
ll od[105][105], nd[105][105];
int main() {
cin >> n >> m >> k;
for(int i=1;i<=n;i++) {
for(int ck=0;ck<k;ck++) {
cin >> b[i][ck] >> s[i][ck];
}
for(int j=1;j<=n;j++) od[i][j]=4e9;
od[i][i]=0;
}
while(m--) {
cin >> a >> bb >> c;
od[a][bb]=c;
adj[a].emplace_back(bb, c);
}
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
od[i][j] = min(od[i][j], od[i][k]+od[k][j]);
while(l < r) {
mid = (l+r)>>1;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) {
nd[i][j]=0;
for(int ck=0;ck<k;ck++) {
if(b[i][ck]==-1||s[j][ck]==-1) continue;
nd[i][j]=max(nd[i][j], s[j][ck]-b[i][ck]);
}
nd[i][j]=od[i][j]*mid-nd[i][j];
}
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
nd[i][j] = min(nd[i][j], nd[i][k]+nd[k][j]);
bool yess=0;
for(int i=1;i<=n;i++) yess |= (nd[i][i]<0);
for(int i=1;i<=n;i++) {
for(auto [dest,dist]:adj[i]) {
yess |= (dist*mid+nd[dest][i]<=0);
}
for(int j=1;j<=n;j++) {
if(i==j) continue;
ll cmx = 0;
for(int ck=0;ck<k;ck++) {
if(b[i][ck]==-1||s[j][ck]==-1) continue;
cmx=max(cmx,s[j][ck]-b[i][ck]);
}
//cout << od[i][j]*mid + nd[j][i] << "\n";
yess |= (od[i][j]*mid-cmx+nd[j][i]<=0);
}
}
if(yess) l = mid+1;
else r = mid;
}
cout << r-1;
}
