#define OPTIMIZE 0
#define Interactive 0
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int INF = 0x3f3f3f3f; // INF = 0x3f3f3f3f, INT_MAX
const long long MOD = 1e9+7; // MOD = 1e9+7, 1e8+7, 998244353
const long long LINF = 1e18;
#define INIT(arr, val) fill(arr, arr+(int)(sizeof(arr)/sizeof(arr[0])), val)
#define REP(i, lb, rb, inc) for(int i = (lb); i < (rb); i += inc)
#define RREP(i, rb, lb, dec) for(int i = (rb)-1; i >= (lb); i -= dec)
#define REPN(i, s, n) for(int i = s; i < n; ++i)
#define RREPN(i, n, s) for(int i = n-1; i >= s; --i)
typedef long long ll;
typedef std::vector<int> VI;
typedef std::vector<ll> VLL;
typedef std::vector<string> VSTR;
#define pb push_back
typedef std::pair<int, int> PII;
typedef std::pair<double, double> PDD;
typedef std::pair<ll, ll> PLL;
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define SZ(x) ((int)(x).size())
#define endl '\n'
#if !Interactive
# define Foxyy cin.tie(0); cout.sync_with_stdio(0); cout.tie(0);
#else
# define Foxyy ;
#endif
#define I_Suck_At_Coding signed main()
#if IDE
# pragma GCC optimize ("trapv")
#endif
#if OPTIMIZE
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,avx,avx2")
#endif
class dummy_ostream : public std::ostream {
public:
dummy_ostream():
std::ostream(&m_sb) {}
private:
class NullBuffer : public std::streambuf {
public:
int overflow(int c) { return c; }
} m_sb;
};
class redirect_ostream {
public:
redirect_ostream(ostream &_os):
os(_os) {}
template<class T>
redirect_ostream& operator << (const T &x) {
os << x;
return *this;
}
private:
ostream &os;
};
class dual_ostream {
public:
dual_ostream(ostream &_os1, ostream &_os2):
os1(_os1), os2(_os2) {}
template<class T>
dual_ostream& operator << (const T &x) {
os1 << x;
os2 << x;
return *this;
}
private:
ostream &os1, &os2;
};
#if IDE && !Interactive
# define Input fin
ifstream fin("cin.in");
ofstream fout("cout.out");
ofstream ferr("cerr.out");
dual_ostream Output(fout, cout);
dual_ostream Error(ferr, cerr);
#else
# define Input cin
redirect_ostream Output(cout);
# if IDE
redirect_ostream Error(cerr);
# else
dummy_ostream Error;
# endif
#endif
#define READ(a, t) t a; Input >> a
#define READARR(arr, n) REP(___i, 0, (n), 1) Input >> arr[___i];
#define PRINTARR(s, arr, n) { REP(___i, 0, (n), 1) s << arr[___i] << " "; s << endl; }
#define RI(a) READ(a, int)
#define RD(a) READ(a, double)
#define RC(a) READ(a, char)
#define RLL(a) READ(a, ll)
#define RSTR(a) READ(a, string)
#define RVI(__a, n) VI __a(n); READARR(__a, n)
#define RVLL(__a, n) VLL __a(n); READARR(__a, n)
#define RVSTR(__a, n) VSTR __a(n); READARR(__a, n)
#define randInt(l, r) uniform_int_distribution<int>(l, r-1)(rng)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int g[MAXN][MAXN];
int g2[MAXN][MAXN];
int profit[MAXN][MAXN];
int B[MAXN][1000], S[MAXN][1000];
int N, M, K;
void floyd_warshall(int g[MAXN][MAXN]) {
REPN(k, 0, N) REPN(i, 0, N) REPN(j, 0, N)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
void init() {
fill(g[0], g[MAXN-1]+MAXN, INF);
Input >> N >> M >> K;
REPN(i, 0, N)
REPN(k, 0, K)
Input >> B[i][k] >> S[i][k];
REPN(i, 0, M) {
RI(a); RI(b); RI(c);
g[a-1][b-1] = c;
}
floyd_warshall(g);
REPN(i, 0, N) REPN(j, 0, N) REPN(k, 0, K)
if (B[i][k] != -1 and S[j][k] != -1)
profit[i][j] = max(profit[i][j], S[j][k] - B[i][k]);
}
bool check(ll m) {
REPN(i, 0, N) REPN(j, 0, N)
g2[i][j] = m * min(g[i][j], INF/(int)m) - profit[i][j];
floyd_warshall(g2);
REPN(i, 0, N) if (g2[i][i] <= 0) return true;
return false;
}
void solve() {
ll l = 0, r = INF;
while(l < r-1) {
ll mid = l+r >> 1;
if (check(mid)) l = mid;
else r = mid;
}
Output << l << endl;
}
I_Suck_At_Coding {
Foxyy
int T = 1;
// Input >> T;
while(T--) {
init();
solve();
}
}
