#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long
template <class _T>
bool chmin(_T &x, const _T &y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag = false;
if ( x < y ){
x = y; flag |= true;
}
return flag;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k; cin >> n >> m >> k;
vector <vector<int>> B(n, vector <int> (k)), S(n, vector <int> (k));
for ( int i = 0; i < n; i++ ){
for ( int j = 0; j < k; j++ ){
cin >> B[i][j] >> S[i][j];
}
}
const int inf = 1e9 + 501;
vector <vector<int>> dis(n, vector <int> (n, inf));
for ( int i = 0; i < m; i++ ){
int u, v, t; cin >> u >> v >> t;
dis[--u][--v] = t;
}
auto RunFloyd = [&](auto &d){
for ( int i = 0; i < n; i++ ){
for ( int j = 0; j < n; j++ ){
for ( int k = 0; k < n; k++ ){
chmin(d[j][k], d[j][i] + d[i][k]);
}
}
}
};
RunFloyd(dis);
vector <vector<int>> P(n, vector <int> (n));
for ( int i = 0; i < n; i++ ){
for ( int j = 0; j < n; j++ ){
for ( int _k = 0; _k < k; _k++ ){
if ( B[i][_k] == -1 or S[j][_k] == -1 ){
continue;
}
chmax(P[i][j], -B[i][_k] + S[j][_k]);
}
}
}
auto ok = [&](int M){
auto a = P;
for ( int i = 0; i < n; i++ ){
for ( int j = 0; j < n; j++ ){
a[i][j] = M * dis[i][j] - P[i][j];
}
}
RunFloyd(a);
bool flag = false;
for ( int i = 0; i < n; i++ ){
flag |= (a[i][i] <= 0);
}
return flag;
};
int l = 0, r = 1e9 + 1;
while ( l + 1 < r ){
int md = (l + r) >> 1;
if ( ok(md) ) l = md;
else r = md;
}
cout << l;
cout << '\n';
}
