#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int inf = 1e18,N = 3e5+1,MOD = 998244353,BL = 1000;
void solve() {
int n,m,k;
cin >> n >> m >> k;
int b[n+1][k+1],s[n+1][k+1];
for (int i=1;i<=n;i++) {
for (int j = 1;j<=k;j++) {
cin >> b[i][j] >> s[i][j];
if (b[i][j] == -1) b[i][j] = inf;
if (s[i][j] == -1) s[i][j] = -inf;
}
}
int profit[n+1][n+1]{};
for (int i=1;i<=n;i++) {
for (int j = i+1;j<=n;j++) {
for (int p = 1;p<=k;p++) {
profit[i][j] = max(profit[i][j],s[j][p]-b[i][p]);
profit[j][i] = max(profit[j][i],s[i][p]-b[j][p]);
}
}
}
int d[n+1][n+1];
for (int i=0;i<=n;i++) for (int j = 0;j<=n;j++) d[i][j] = inf;
for (int i=1;i<=n;i++) d[i][i] = 0;
for (int i=1;i<=m;i++) {
int a,b,c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b],c);
}
for (int i=1;i<=n;i++) {
for (int j = 1;j<=n;j++) {
for (int k = 1;k<=n;k++) {
d[j][k] = min(d[j][k],d[j][i]+d[i][k]);
d[k][j] = min(d[k][j],d[k][i]+d[i][j]);
}
}
}
int go[n+1][n+1];
pii lp[n+1],lp2[n+1];
int l = 0;
int r = 1e9;
while (l<=r){
int w = (l+r) >> 1;
for (int i=1;i<=n;i++) {
lp[i] = {0,0};
for (int j = 1;j<=n;j++) {
go[i][j] = max(-inf,profit[i][j]-w*d[i][j]);
}
}
bool yes = 0;
for (int ii=1;ii<=n;ii++) {
for (int i=1;i<=n;i++) lp2[i] = lp[i];
bool fl = 0;
for (int i = 1;i<=n;i++) {
for (int j = 1;j<=n;j++) {
if (i == j) continue;
if (lp[j].ff >= inf) continue;
if (pii{lp2[i].ff+go[i][j],lp2[i].ss+1} > lp[j]) {
lp[j] = {lp2[i].ff+go[i][j],lp2[i].ss+1};
fl = 1;
}
}
}
if (ii == n && fl) {
yes = 1;
}
}
if (!yes) r = w-1;
else l = w+1;
}
cout << r << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
