#include <bits/stdc++.h>
#include <vector>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 100;
const int MAX_K = 1000;
const int INF = 0x3f3f3f3f;
int d[MAX_N][MAX_N];
pii price[MAX_N][MAX_K];
int max_profit[MAX_N][MAX_N];
void solve() {
int n, m, k;
cin >> n >> m >> k;
for (int i=0; i<n; ++i) {
for (int j=0; j<k; ++j) {
cin >> price[i][j].first >> price[i][j].second;
}
}
for (int i=0; i<MAX_N; ++i) {
for (int j=0; j<MAX_N; ++j) {
d[i][j] = (i == j ? 0 : INF);
}
}
for (int i=0; i<m; ++i) {
int v, w, t;
cin >> v >> w >> t;
d[v-1][w-1] = t;
}
for (int k=0; k<n; ++k) {
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
for (int l=0; l<k; ++l) {
if (price[i][l].first != -1 && price[j][l].second != -1) {
max_profit[i][j] = max(max_profit[i][j], price[j][l].second - price[i][l].first);
}
}
}
}
int l = 0, r = INF;
while (l < r) {
int m = (l+r+1) / 2;
vector<tuple<int, int, ll>> edges;
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (i != j && d[i][j] < INF) {
ll minw = 4e18;
for (int p=0; p<n; ++p) {
if (d[i][p] < INF && d[p][j] < INF) {
minw = min(minw, (ll)m * (d[i][p] + d[p][j]) - max_profit[i][p]);
}
}
edges.push_back({ i, j, minw });
}
}
}
// print(edges);
bool neg_cycle = false;
vector<ll> dist(n, 4e18);
for (int i=0; i<n; ++i) {
bool reduced = false;
for (auto[a,b,w]: edges) {
if (dist[b] > dist[a] + w) {
dist[b] = dist[a] + w;
reduced = true;
}
}
if (i == n-1 && reduced) neg_cycle = true;
}
if (!neg_cycle) {
vector<vector<int>> adj(n);
for (auto[a,b,w]: edges) {
if (dist[b] == dist[a] + w) adj[a].push_back(b);
}
bool cycle_exist = false;
vector<int> visited(n, -1);
for (int i=0; i<n; ++i) {
if (visited[i] == -1) {
queue<int> q;
visited[i] = 0;
q.push(i);
while (!q.empty()) {
int here = q.front();
q.pop();
for (int there: adj[here]) {
if (visited[there] != -1) {
if (visited[there] < visited[here]) cycle_exist = true;
} else {
q.push(there);
visited[there] = visited[here] + 1;
}
}
if (cycle_exist) break;
}
if (cycle_exist) break;
}
}
if (cycle_exist) {
l = m;
} else {
r = m-1;
}
} else {
l = m;
}
}
cout << l;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
