#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
const ll maxn = 100;
const ll maxk = 1000;
ll b[maxn][2*maxk], s[maxn][2*maxk];
ll dis[maxn][maxn];
ll dis_now[maxn][maxn];
ll profit[maxn][maxn];
ll INF = 1e18;
void floyd_warshal(ll adg[maxn][maxn]) {
for (ll i = 0; i < maxn; i++) {
for (ll j = 0; j < maxn; j++) {
for (ll k = 0; k < maxn; k++) {
adg[j][k] = min(adg[j][k], adg[j][i] + adg[i][k]);
}
}
}
}
ll solve() {
ll n, m, k;
cin >> n >> m >> k;
for (ll i = 0; i < maxn; i++) {
for (ll j = 0; j < 2 * maxk; j++) {
b[i][j] = -1, s[i][j] = -1;
}
}
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < 2 * k; j += 2) {
cin >> b[i][j/ 2];
cin >> s[i][j / 2];
}
}
for (ll i = 0; i < maxn; i++) {
for (ll j = 0; j < maxn; j++) {
dis[i][j] = INF;
}
}
for (ll i = 0; i < m; i++) {
ll v, u, t;
cin >> v >> u >> t;
v--, u--;
dis[v][u] = t;
}
floyd_warshal(dis);
for (ll i = 0; i < maxn; i++) {
for (ll j = 0; j < maxn; j++) {
profit[i][j] = 0;
for (ll p = 0; p < k; p++) {
if (b[i][p] != -1 && s[j][p] != -1) {
profit[i][j] = max(profit[i][j], s[j][p] - b[i][p]);
}
}
}
}
ll start = 0, end = 1e12;
ll pos = 0;
while (start <= end) {
ll mid = (start + end) / 2;
for (ll i = 0; i < maxn; i++) {
for (ll j = 0; j < maxn; j++) {
dis_now[i][j] = mid * min(dis[i][j], mid == 0 ? INF : INF / mid) - profit[i][j];
}
}
floyd_warshal(dis_now);
bool f = false;
for (ll i = 0; i < maxn; i++) {
if (dis_now[i][i] <= 0) {
f = true; break;
}
}
if (f) {
pos = mid;
start = mid + 1;
}
else {
end = mid - 1;
}
}
return pos;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << solve();
}
