#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define iter(id, v) for(auto id : v)
#define fs first
#define se second
#define MP make_pair
#define pb push_back
#define bit(msk, i) ((msk >> i) & 1)
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 1e2 + 7;
const int KK = 1e3 + 7;
const int M = 1e4 + 7;
const int Mod = 1e9 + 2022;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 350;
int n, m, K;
pll a[N][KK];
ll Dist[N][N], dp[N][N];
struct Edge {
ll u, v, w;
};
ll D[N], Dist2[N][N];
bool Find_positive_cycle (vector<Edge> &edges) {
rep (i, 1, n) D[i] = 0;
rep (step, 1, n) {
iter (&id, edges){
int u = id.u, v = id.v;
ll w = id.w;
if (D[v] < D[u] + w) {
D[v] = D[u] + w;
}
}
}
rep (step, 1, n) {
iter (&id, edges){
int u = id.u, v = id.v;
ll w = id.w;
if (D[v] < D[u] + w) {
// cout << u <<" "<<v<< " "<<D[v] <<" "<<D[u] <<" a a\n";
return 1;
}
}
}
rep (i, 1, n) rep (j, 1, n) Dist2[i][j] = -INF;
iter (&id, edges) {
Dist2[id.u][id.v] = id.w;
}
rep (k, 1, n)
rep (i, 1, n)
rep (j, 1, n) Dist2[i][j] = max(Dist2[i][j], Dist2[i][k] + Dist2[k][j]);
rep (i, 1, n) rep (j, 1, n) if (Dist2[i][j] > -INF && Dist2[j][i] > -INF && Dist2[i][j] + Dist2[j][i] >= 0) {
// cout << i <<" "<<j<<" "<<Dist2[i][j] <<" "<<Dist2[j][i] <<"\n";
return 1;
}
return 0;
}
bool check (ll X) {
static vector<Edge> edges; edges.clear();
rep (i, 1, n)
rep (j, 1, n) {
if (i != j && dp[i][j] > -INF && Dist[i][j] < INF) {
edges.pb ({i, j, dp[i][j] - Dist[i][j] * X});
// cout << i << " "<<j<<" "<<dp[i][j] - Dist[i][j] * X<<"\n";
}
}
return Find_positive_cycle (edges);
}
void BS (ll L, ll R) {
while (L < R) {
ll mid = L + R + 1>> 1;
if (check(mid)) L = mid;
else R = mid - 1;
}
cout << L <<"\n";
}
void solution() {
cin >> n >> m >> K;
rep (i, 1, n) {
rep (j, 1, K ) {
cin >> a[i][j].fs >> a[i][j].se;
}
}
rep (i, 1, n) rep (j, 1, n) Dist[i][j] = INF;
rep (i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
Dist[u][v] = w;
}
rep (k, 1, n)
rep (i, 1, n)
rep (j, 1, n) Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]);
bool ok = 0;
rep (i, 1, n) rep (j, 1, n) if (i != j && Dist[i][j] < INF && Dist[j][i] < INF) {
ok = 1;
}
rep (i, 1, n)
rep (j, 1, n) {
rep (k, 1, K) {
if (a[i][k].fs != -1 && a[j][k].se != -1) {
dp[i][j] = max(dp[i][j], -a[i][k].fs + a[j][k].se);
}
}
}
if (!ok) {
cout << 0 <<"\n";
return;
}
// cout << check(2) <<" a\n";
// return;
BS(0, 1e16);
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug +5
9 6
7 6
9 1
2 4
4 5
9 2
8 6
9 3
8 1
3
1
6
4
4
2
5
5
6
*/
