#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
const char nl = '\n';
void fastIO() {
ios::sync_with_stdio(false);
cin.tie(0);
}
int N, M, K;
vector<vi> opt(vector<vi> adj) { // adjacency matrix of distance, optimize
vector<vi> res = adj;
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res[i][j] = min(res[i][j], res[i][k] + res[k][j]);
res[i][j] = max(res[i][j], (ll)(-1e18));
}
}
}
return res;
}
int main() {
fastIO();
cin>>N>>M>>K;
vector<vi> buy(N, vi(K, -1)); // buying price, higher
vector<vi> sell(N, vi(K, -1)); // selling price, lower
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
cin>>buy[i][j]>>sell[i][j];
}
}
vector<vi> adj(N, vi(N, 1e18));
for (int i = 0; i < M; i++) {
int u, v; ll w;
cin>>u>>v>>w;
u--; v--;
adj[u][v] = w;
}
adj = opt(adj);
/* cout<<"adj: "<<endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout<<adj[i][j]<<" ";
}
cout<<endl;
}*/
vector<vi> profit(N, vi(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < K; k++) {
if (sell[j][k] != -1 && buy[i][k] != -1)
profit[i][j] = max(profit[i][j], sell[j][k] - buy[i][k]);
}
}
}
/* cout<<"profit: "<<endl;
for (vi v : profit) {
for (ll x : v)
cout<<x<<" ";
cout<<endl;
}*/
ll low = 0;
ll high = 1e18;
ll ans = -1;
// maximum k so has nonpos cyc where each edge as k * dist - profit
// "nonpositive loss", paid per time
while (low <= high) { // true, true, true, false, false, false
ll mid = (low + high) / 2;
vector<vi> adjc(N, vi(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
adjc[i][j] = mid * min(adj[i][j], (ll)(2e18) / mid) - profit[i][j];
}
}
/* cout<<"adjc before: "<<endl;
for (vi v : adjc) {
for (ll x : v)
cout<<x<<" ";
cout<<endl;
}*/
adjc = opt(adjc);
/* cout<<"adjc after: "<<endl;
for (vi v : adjc) {
for (ll x : v)
cout<<x<<" ";
cout<<endl;
}*/
// if any node to itself is <= 0, then works
bool works = false;
for (int i = 0; i < N; i++) {
if (adjc[i][i] <= 0)
works = true;
}
if (works) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
// cout<<"ANSWER: ";
cout<<ans<<endl;
}
