#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 = INF(ll) >> 4ll;
/*
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(dur[i][j] >= INT_INF || dur[j][i] >= INT_INF) continue;
if(i == j) continue;
dist[i][j] = M * min(dur[i][j], INT_INF / M) - profits[i][j];
}
}
// Apply Floyd-warshall
// for(ll rep = 0ll; rep < 2ll; rep++) {
for(ll k = 0ll; k < n; k++) {
for(ll i = 0ll; i < n; i++) {
for(ll j = 0ll; j < n; j++) {
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++) {
// cerr << dist[i][j] << " ";
// }
// cerr << "\n";
// }
// cerr << "\n";
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 k = 0ll; k < n; k++) {
for(ll i = 0ll; i < n; i++) {
for(ll j = 0ll; j < n; j++) {
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++) {
if(market[j][kp].second != -1ll && market[i][kp].first != -1ll) profits[i][j] = max(profits[i][j], market[j][kp].second - market[i][kp].first);
}
}
}
/// Shortest paths
ll l = -1ll, r = 1'000'000'001ll;
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;
}
