#define _GLIBCXX_DEBUG_PEDANTIC
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define dbg(x) cerr << #x << ": " << x << endl;
const int INF = 2e9;
const int MAX_N = 100;
const int MAX_K = 1000;
const long double EPS = 1e-9;
int b[MAX_N][MAX_K];
int s[MAX_N][MAX_K];
int max_earn[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];
long double new_dist[MAX_N][MAX_N];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
for (int v = 0; v < n; ++v) {
for (int i = 0; i < k; ++i) {
cin >> b[v][i] >> s[v][i];
}
}
for (int i = 0; i < MAX_N; ++i) {
for (int j = 0; j < MAX_N; ++j) {
dist[i][j] = INF;
}
}
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
int w;
cin >> w;
dist[u][v] = w;
}
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
for (int i = 0; i < k; ++i) {
if (s[v][i] == -1 || b[u][i] == -1) continue;
max_earn[u][v] = max(max_earn[u][v], s[v][i] - b[u][i]);
}
}
}
for (int w = 0; w < n; ++w) {
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
dist[u][v] = min(dist[u][v], dist[u][w] + dist[w][v]);
}
}
}
auto check = [&](long double x) -> bool {
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
if (dist[u][v] == INF) {
new_dist[u][v] = -INF;
} else {
new_dist[u][v] = max_earn[u][v] - x * dist[u][v];
}
}
}
for (int w = 0; w < n; ++w) {
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
if (new_dist[u][w] <= -INF || new_dist[w][v] <= -INF) continue;
new_dist[u][v] = max(new_dist[u][v], new_dist[u][w] + new_dist[w][v]);
}
}
}
return new_dist[0][0] >= EPS;
};
int l = 0;
int r = 1e8;
while (l != r - 1) {
int mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
cout << l << '\n';
return 0;
}
