#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k;
int INF = 2 * 1e9;
vector<vector<pair<int, int>>> markets; vector<vector<int>> gr; vector<vector<int>> profits;
vector<bool> used;
struct Edge {
int from, to, w;
Edge(int from, int to, int w) : from(from), to(to), w(w) {}
};
void dfs(int v) {
used[v] = true;
for (auto u : gr[v]) {
if (!used[u]) {
dfs(u);
}
}
}
int main() {
cin >> n >> m >> k; markets.resize(n, vector<pair<int, int>>(k));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
cin >> markets[i][j].first; cin >> markets[i][j].second;
}
}
gr.resize(n); vector<Edge> edges;
for (int i = 0; i < m; i++) {
int v, u, t; cin >> v >> u >> t; v--; u--;
gr[v].push_back(u); edges.push_back(Edge(v, u, t));
}
profits.assign(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int x = 0; x < k; x++) {
if (markets[i][x].second != -1 && markets[j][x].first != -1 && profits[i][x] != INF && profits[x][j] != INF) {
profits[i][j] = max(profits[i][j], -markets[i][x].first + markets[j][x].second);
}
}
}
}
/*
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << "profits[" << i << "][" << j << "] = " << profits[i][j] << endl;
}
}
*/
int l = -1; int h = 2 * 1e9;
while (l + 1 < h) {
int m = (l + h) / 2;
vector<vector<int>> d(n, vector<int>(n, INF));
for (int i = 0; i < n; i++) {
d[i][i] = 0;
}
for (auto& e : edges) {
d[e.from][e.to] = min(d[e.from][e.to], m * e.w - profits[e.from][e.to]);
}
for (int x = 0; x < n; x++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (d[i][x] != INF && d[x][j] != INF) {
d[i][j] = min(d[i][j], d[i][x] + d[x][j]);
}
}
}
}
int cycles = 0;
for (int i = 0; i < n; i++) {
if (d[i][i] < 0) {
cycles = 1;
}
}
if (cycles == 1) {
l = m;
}
else {
h = m;
}
}
cout << h << "\n";
}
