#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef set<int> si;
typedef set<long long> sll;
const ll MOD = 998244353;
const ld EPS = 1e-12;
#define endl "\n"
#define sp <<" "<<
#define forn(i, n) for(ll i = 0; i < n; i++)
#define rforn(i, n) for(ll i = n; i >= 0; i--)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 1e9+21
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
void solution() {
ll n, m, k; cin >> n >> m >> k;
vector<vector<pair<ll, ll>>> bs(n, vector<pair<ll, ll>>(k)); // haha bs
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
cin >> bs[i][j].first >> bs[i][j].second;
}
}
ll dist[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
for (int i = 0; i < m; i++) {
int v, w, t; cin >> v >> w >> t;
v--; w--;
dist[v][w] = t;
}
// dist between any two nodes
for (int l = 0; l < n; l++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);
}
}
}
// profit between any two nodes
ll profit[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
profit[i][j] = 0;
for (int l = 0; l < k; l++) {
if (bs[i][l].first == -1 || bs[j][l].second == -1) continue;
profit[i][j] = max(profit[i][j], bs[j][l].second - bs[i][l].first);
}
}
}
// binary search max efficiency
ll eff[n][n];
ll l = 0, r = 1e11+21;
while (l < r) {
ll mid = (l + r) / 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
eff[i][j] = mid * min(dist[i][j], (ll)INF / mid) - profit[i][j];
}
}
// floyd warshall again
for (int kk = 0; kk < n; kk++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
eff[i][j] = min(eff[i][j], eff[i][kk] + eff[kk][j]);
}
}
}
bool ok = false;
for (int i = 0; i < n; i++) {
if (eff[i][i] <= 0) {
ok = true;
break;
}
}
if (ok) {
l = mid + 1;
} else {
r = mid;
}
}
cout << r << endl;
return;
}
signed main() {
fast_io();
solution();
return 0;
}
