/*
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
\\ //
// 271828___182845__904523__53602__ \\
\\ 87___47____13______52____66__24_ //
// 97___75____72______47____09___36 \\
\\ 999595_____74______96____69___67 //
// 62___77____24______07____66__30_ \\
\\ 35___35____47______59____45713__ //
// \\
\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;
vector<int> dx = {1, 0, 0, -1, 1, 1, -1, -1};
vector<int> dy = {0, 1, -1, 0, 1, -1, 1, -1};
int n, m, k;
void solve() {
cin >> n >> m >> k;
vector<vector<int>> s(n, vector<int>(k)), b(n, vector<int>(k));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) {
cin >> b[i][j] >> s[i][j];
}
}
vector<vector<pair<int, int>>> gp(n);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
gp[--u].push_back({--v, w});
}
vector<vector<LL>> d(n, vector<LL>(n, inf));
for (int i = 0; i < n; ++i) {
priority_queue<pair<LL, int>> pq;
pq.push({0, i});
while (pq.size()) {
LL ds = -pq.top().first, u = pq.top().second;
pq.pop();
if (ds > d[i][u])
continue;
for (pair<int, int> &v : gp[u]) {
if (ds + v.second < d[i][v.first]) {
d[i][v.first] = ds + v.second;
pq.push({-d[i][v.first], v.first});
}
}
}
}
vector<vector<int>> max_delta(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int mx = 0;
for (int t = 0; t < k; ++t) {
if(s[j][t] == -1 || b[i][t] == -1) continue;
mx = max(mx, s[j][t] - b[i][t]);
}
max_delta[i][j] = mx;
}
}
vector<vector<LL>> d1 = d;
function<void()> max_path = [&](){
for(int k = 0; k < n; ++k){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
d1[i][j] = max(d1[i][j], d1[i][k] + d1[k][j]);
}
}
}
};
LL l = 0, r = 2e9;
while(l + 1 < r){
LL mid = (l + r) / 2;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j){
d1[i][j] = max_delta[i][j] - mid * min(inf / mid, d[i][j]);
}
}
// cout << mid << "\n";
max_path();
for(int i = 0; i < n; ++i){
if(d1[i][i] >= 0) {
l = mid;
}
}
if(l != mid) {
r = mid;
}
}
cout << l << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// int t; cin >> t; while (t--)
solve();
}
