#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 1e2 + 10, MAXK = 1e3 + 10;
const ll INF = 4e18;
ll n, m, k, d[MAXN][MAXN], best[MAXN][MAXN], b[MAXN][MAXK], s[MAXN][MAXK];
ll d1[MAXN], d2[MAXN];
ld d3[MAXN], d4[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++)
d1[i] = d2[i] = 0;
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < n; j++) {
for (auto p : adj[j])
d1[p.first] = max(d1[p.first], d1[j] - x * p.second);
for (int y = 0; y < n; y++)
if (d[j][y] != INF)
d1[y] = max(d1[y], d1[j] + best[j][y] - x * d[j][y]);
}
if (i == (n - 1)) {
for (int j = 0; j < n; j++)
d2[j] = d1[j];
}
}
for (int i = 0; i < n; i++)
if (d1[i] != d2[i])
return true;
return false;
}
bool check1(ld x) {
for (int i = 0; i < n; i++)
d3[i] = d4[i] = 0;
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < n; j++) {
for (auto p : adj[j])
d3[p.first] = max(d3[p.first], d3[j] - x * p.second);
for (int y = 0; y < n; y++)
if (d[j][y] != INF)
d3[y] = max(d3[y], d3[j] + best[j][y] - x * d[j][y]);
}
if (i == (n - 1)) {
for (int j = 0; j < n; j++)
d4[j] = d3[j];
}
}
for (int i = 0; i < n; i++)
if (d3[i] != d4[i])
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 (check1((ld)r - (1e-6))? r: 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
*/
