#include <bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>
inline bool maxi(T &x, const T &val)
{
if (x < val) return x = val, true;
return false;
}
template<typename T>
inline bool mini(T &x, const T &val)
{
if (x > val) return x = val, true;
return false;
}
const int maxn = 110, maxk = 1010, oo = 1e18;
int n, m, k;
int b[maxn][maxk], s[maxn][maxk];
vector<pair<int,int> > adj[maxn];
int d[maxn][maxn];
int pro[maxn][maxn];
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
void Dijkstra(int st, int d[])
{
d[st] = 0;
pq.push({0, st});
while (!pq.empty()) {
int wei = pq.top().first;
int cur = pq.top().second;
pq.pop();
if (d[cur] != wei) continue;
for (auto [v, w] : adj[cur]) {
if (mini(d[v], wei + w)) {
pq.push({d[v], v});
}
}
}
}
int dp[maxn][maxn];
bool check(int mid)
{
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = pro[i][j] - mid * d[i][j];
}
}
for (int x = 1; x <= n; x++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
maxi(dp[i][j], dp[i][x] + dp[x][j]);
}
}
}
for (int i = 1; i <= n; i++) {
if (dp[i][i] >= 0) {
return true;
}
}
return false;
}
void solve()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
cin >> b[i][j] >> s[i][j];
}
}
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
memset(d, 60, sizeof d);
for (int i = 1; i <= n; i++) {
Dijkstra(i, d[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
pro[i][j] = -oo;
continue;
}
int &tmp = pro[i][j];
for (int x = 1; x <= k; x++) {
if (s[j][x] != -1 && b[i][x] != -1 && s[j][x] > b[i][x]) {
maxi(tmp, s[j][x] - b[i][x]);
}
}
}
}
int l = 0;
int r = 1e9;
int ans = l;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans << '\n';
}
signed main()
{
#ifdef LOCAL
clock_t st = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
#define Task ""
#ifdef LOCAL
if (!fopen("D:\\.inp", "r")) {
freopen("D:\\.inp", "w", stdout);
freopen("D:\\.out", "w", stdout);
cerr << "get input from file\n";
return 0;
}
freopen("D:\\.inp", "r", stdin);
freopen("D:\\.out", "w", stdout);
#else
if (fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
#endif
solve();
#ifdef LOCAL
cerr << clock() - st << endl;
#endif
}
