#include<bits/stdc++.h>
using namespace std;
#include<fstream>
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#define pii pair<int, int>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll mod= 1e9 + 7;
const int mxq = 105, sq = 750, mxn = 105;
ll best[mxn + 1][mxn + 1], d[mxn + 1][mxn + 1], s[mxn + 1][mxn + 1], b[mxn + 1][mxn + 1];
int n, m, k;
struct e{
ll u, v, w;
};
vt<e>edge;
bool ck(ll mid){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
d[i][j] = 1e18;
}
}
for(auto [u, v, w]: edge){
d[u][v] = min(d[u][v], w * mid - best[u][v]);
// cout << u << ' ' << v << " " << w * mid - best[u][v] << "\n";
}
for(int l = 1; l <= n; l++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(d[i][l] != 1e18 && d[l][j] != 1e18){
d[i][j] = min(d[i][j], d[i][l] + d[l][j]);
}
}
}
}
for(int i = 1; i <= n; i++){
if(d[i][i] <= 0)return(true);
}
return(false);
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
cin >> b[i][j] >> s[i][j];
}
}
forr(i, 0, m){
int u, v, w; cin >> u >> v >> w;
edge.pb({u, v, w});
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i == j)continue;
for(int l = 1; l <= k; l++){
if(s[i][l] == -1 || b[j][l] == -1)continue;
best[i][j] = max(best[i][j], s[j][l] - b[i][l]);
}
}
}
ll l = 1, r = 1e9, ans;
while(l <= r){
ll mid = l + (r - l) / 2;
if(ck(mid)){
ans = mid; l = mid + 1;
}else{
r = mid - 1;
}
}
cout << ans;
return(0);
}
