#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e2 + 10, MAXK = 1e3 + 10;
const ll INF = 2e18;
ll n, m, k, d[MAXN][MAXN], best[MAXN][MAXN], b[MAXN][MAXK], s[MAXN][MAXK];
ll d1[MAXN][MAXN];
vector<pair<ll, ll>> adj[MAXN];
void input() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = INF;
for (int i = 0; i < n; i++)
d[i][i] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++)
cin >> b[i][j] >> s[i][j];
for (int i = 0; i < m; i++) {
ll u, v, w;
cin >> u >> v >> w;
d[--u][--v] = w;
adj[u].push_back({v, w});
}
}
void findDist() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int x = 0; x < n; x++)
d[j][x] = min(d[j][x], d[j][i] + d[i][x]);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int x = 0; x < k; x++)
if (b[i][x] != -1 && s[j][x] != -1)
best[i][j] = max(best[i][j], s[j][x] - b[i][x]);
}
bool check(ll x) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d1[i][j] = -INF;
for (int i = 0; i < n; i++) {
for (auto p : adj[i])
d1[i][p.first] = -x * p.second;
for (int j = 0; j < n; j++)
if (d[i][j] != INF && j != i)
d1[i][j] = max(d1[i][j], best[i][j] - x * d[i][j]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
for (int x = 0; x < n; x++)
d1[j][x] = max(d1[j][x], d1[j][i] + d1[i][x]);
for (int j = 0; j < n; j++)
if (d1[j][j] >= 0)
return true;
}
return false;
}
ll findAns() {
ll l = 0, r = 1e9;
while (r - l > 1) {
ll mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
return l;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
input();
findDist();
cout << findAns() << endl;
return 0;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/
