#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
#define pb push_back
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
const ll BUY_MAX = 1'000'000'000ll;
const ll SELL_MIN = 0ll;
const ll INT_INF = (ll)INF(int);
/*
check if the graph with weights M*dur - profit
has a nonpositive cycle
*/
bool good(ll n, ll m, ll k, ll M, const vvll& dur, const vvll& profits) {
vvll dist;
for(ll i = 0ll; i < n; i++) {
vll distr(n, INT_INF);
dist.pb(distr);
}
// Initialize distance array
for(ll i = 0ll; i < n; i++) {
for(ll j = 0ll; j < n; j++) {
if(i == j) continue;
dist[i][j] = M * dur[i][j] - profits[i][j];
}
}
// Apply Floyd-warshall
for(ll i = 0ll; i < n; i++) {
for(ll j = 0ll; j < n; j++) {
for(ll k = 0ll; k < n; k++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
for(ll i = 0ll; i < n; i++) {
for(ll j = 0ll; j < n; j++) {
for(ll k = 0ll; k < n; k++) {
if(dist[i][k] + dist[k][j] < dist[i][j]) {
// Found negative cycle, return
return true;
}
}
}
}
for(ll i = 0ll; i < n; i++) if(dist[i][i] == 0ll) return true;
return false;
}
int main() {
ll n, m, k;
cin >> n >> m >> k;
// Input the prices
vvpll market;
for(ll i = 0ll; i < n; i++) {
vpll prices;
for(ll j = 0ll; j < k; j++) {
ll b, s;
cin >> b >> s;
if(b == -1ll) b = BUY_MAX;
if(s == -1ll) s = SELL_MIN;
prices.pb({b, s});
}
market.pb(prices);
}
// Input the weights in the adjacency matrix
vvll dist;
for(ll i = 0ll; i < n; i++) {
vll distr(n, INT_INF);
dist.pb(distr);
}
for(ll i = 0ll; i < n; i++) dist[i][i]= 0ll;
for(ll i = 0ll; i < m; i++) {
ll u, v, w;
cin >> u >> v >> w;
u--; v--;
dist[u][v] = w;
}
for(ll i = 0ll; i < n; i++) {
for(ll j = 0ll; j < n; j++) {
if(i == j) continue;
for(ll k = 0ll; k < n; k++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// Preprocess shortest paths and max profits
vvll profits;
for(ll i = 0ll; i < n; i++) {
vll profitsr(n, 0ll);
profits.pb(profitsr);
}
// profits[buy][sell]
for(ll i = 0ll; i < n; i++) {
for(ll j = 0ll; j < n; j++) {
if(i == j) continue;
for(ll kp = 0ll; kp < k; kp++) {
profits[i][j] = max(profits[i][j], market[j][kp].second - market[i][kp].first);
}
}
}
/// Shortest paths
ll l = -1ll, r = INT_INF;
while(r - l > 1ll) {
ll M = (l + r) >> 1ll;
if(good(n, m, k, M, dist, profits)) l = M;
else r = M;
}
cout << max(l, 0ll) << endl;
return 0;
}
