#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
using namespace std;
typedef long long ll;
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll LLINF = 1e9 + 5;
bool existsNegativeLoop(ll x, const vector<vector<ll>>& profit, const vector<vector<ll>>& dist) {
int n = profit.size();
vector<vector<ll>> gr(n, vector<ll>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
gr[i][j] = x * dist[i][j] - profit[i][j];
}
}
for (int i = 0; i < n; ++i) {
gr[i][i] = LLINF;
}
for (int q = 0; q < n; ++q) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
gr[i][j] = min(gr[i][j], gr[i][q] + gr[q][j]);
}
}
}
for (int i = 0; i < n; ++i) {
if (gr[i][i] <= 0) {
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<ll>> buy(n, vector<ll>(k));
vector<vector<ll>> sell(n, vector<ll>(k));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) {
cin >> buy[i][j] >> sell[i][j];
}
}
vector<vector<ll>> matr(n, vector<ll>(n, LLINF));
for (int i = 0; i < m; ++i) {
int u, v;
ll t;
cin >> u >> v >> t;
matr[u - 1][v - 1] = t;
}
for (int i = 0; i < n; ++i) {
matr[i][i] = 0;
}
vector<vector<ll>> dist = matr;
for (int q = 0; q < n; ++q) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dist[i][j] = min(dist[i][j], dist[i][q] + dist[q][j]);
}
}
}
vector<vector<ll>> profit(n, vector<ll>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j || dist[i][j] == LLINF) {
continue;
}
for (int q = 0; q < k; ++q) {
if (buy[i][q] == -1 || sell[j][q] == -1) {
continue;
}
profit[i][j] = max(profit[i][j], sell[j][q] - buy[i][q]);
}
}
}
ll l = 0, r = 1e9;
while (r - l > 1) {
ll m = (l + r) / 2;
if (existsNegativeLoop(m, profit, dist)) {
l = m;
} else {
r = m;
}
}
cout << l << '\n';
}
