//
// Created by mihai145 on 24.02.2021.
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 100;
const int KMAX = 1000;
const long long INF = 1e9;
int N, M, K;
long long buy[NMAX + 2][KMAX + 2], sell[NMAX + 2][KMAX + 2];
long long bestProfit[NMAX + 2][NMAX + 2];
long long minTime[NMAX + 2][NMAX + 2];
void CalcBestProfit() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i != j) {
//bestProfit[i][j] = 0;
for (int k = 1; k <= K; k++) {
if (sell[j][k] != -1 && buy[i][k] != -1) {
bestProfit[i][j] = max(bestProfit[i][j], sell[j][k] - buy[i][k]);
}
}
}
}
}
}
void CalcMinTime() {
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if(minTime[i][k] != INF && minTime[k][j] != INF)
minTime[i][j] = min(minTime[i][j], minTime[i][k] + minTime[k][j]);
}
}
}
}
vector<pair<int, long long>> g[NMAX + 2];
long long cost[NMAX + 2];
int impr[NMAX + 2];
bool inQ[NMAX + 2];
bool MoreThan(long long R) {
for (int i = 1; i <= N; i++) {
g[i].clear();
cost[i] = INF;
impr[i] = 0;
inQ[i] = false;
for (int j = 1; j <= N; j++) {
g[i].push_back({j, -bestProfit[i][j] + R * minTime[i][j]});
}
}
queue<int> q;
q.push(1);
cost[1] = 0;
inQ[1] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
inQ[node] = false;
for (auto it : g[node]) {
if (cost[it.first] > cost[node] + it.second) {
cost[it.first] = cost[node] + it.second;
if (!inQ[it.first]) {
q.push(it.first);
inQ[it.first] = true;
impr[it.first]++;
if (impr[it.first] > N) {
return true; ///NEGATIVE COST CYCLE
}
}
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> K;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
cin >> buy[i][j] >> sell[i][j];
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
minTime[i][j] = INF;
}
}
for (int i = 1; i <= M; i++) {
int u, v, t;
cin >> u >> v >> t;
minTime[u][v] = t;
}
CalcBestProfit();
CalcMinTime();
/*
cout << "BEST PROFIT\n";
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
cout << bestProfit[i][j] << " ";
}
cout << '\n';
}
cout << "\n\n\n";
cout << "MIN TIME\n";
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
cout << minTime[i][j] << " ";
}
cout << '\n';
}
cout << "\n\n\n";
*/
long long st = 0, dr = INF, sol = 0;
while (st <= dr) {
long long mid = (st + dr) >> 1;
if (MoreThan(mid)) {
sol = mid + 1;
st = mid + 1;
} else {
dr = mid - 1;
}
}
cout << sol << '\n';
return 0;
}
