#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <sstream>
using namespace std;
using int64 = long long;
const double EPS = 1e-9;
const int INF = (1<<30);
struct Market {
int b;
int s;
};
int N, M, K;
vector<vector<Market>> market;
vector<vector<int>> dist;
vector<vector<pair<int, int>>> edges;
bool go(long double r) {
vector<long double> d(N, 1e18);
d[0] = 0;
for (int steps = 0; steps <= N; steps++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (dist[i][j] != INF) {
long double w =
edges[i][j].second - edges[i][j].first * r;
// cerr << edges[i][j].second << " -> " << edges[i][j].first << "\n";
if (d[j] > d[i] + w + EPS) {
if (steps == N) {
// negative cycle
return true;
}
d[j] = d[i] + w;
}
}
}
}
// for (int i = 0; i < N; i++) {
// cerr << d[i] << " ";
// }
// cerr << "\n";
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> K;
market = vector<vector<Market>>(N, vector<Market>(K));
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
cin >> market[i][j].b >> market[i][j].s;
}
}
dist = vector<vector<int>>(N, vector<int>(N, INF));
for (int i = 0; i < M; i++) {
int x, y, w;
cin >> x >> y >> w;
x--, y--;
dist[x][y] = min(dist[x][y], w);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (i != k && k != j && j != i && dist[i][k] < INF && dist[k][j] < INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
edges = vector<vector<pair<int, int>>>(N, vector<pair<int, int>>(N, {0, 0}));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (dist[i][j] < INF) {
// i -> j
int up = 0;
for (int k = 0; k < K; k++) {
if (market[i][k].b != -1 && market[j][k].s != -1) {
up = max(up, market[j][k].s - market[i][k].b);
}
}
edges[i][j] = {up, dist[i][j]};
}
}
}
long double l = 1e-9, r = 1e18;
while (l + EPS <= r) {
auto m = (l + r) / 2;
// cerr << l << " " << r << "\n";
if (go(m)) {
r = m;
} else {
l = m;
}
}
auto inv = 1.0 / l;
cout << (int64) inv << "\n";
return 0;
}
