#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
#define int long long
int distgraph[100][100], profitgraph[100][100], dumbgraph[100][100], n, m, k;
pair<int,int> goods[100][1000];
bool checkans(int a) {
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
dumbgraph[i][j] = distgraph[i][j] * a - profitgraph[i][j];
}
}
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
for (int l=0;l<n;l++) {
dumbgraph[j][l] = min(dumbgraph[j][l], dumbgraph[j][i] + dumbgraph[i][l]);
}
}
}
for (int i=0;i<n;i++) {
if (dumbgraph[i][i]<= 0) return true;
}
return false;
}
void distcalc() {
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
for (int l=0;l<n;l++) {
distgraph[j][l] = min(distgraph[j][l], distgraph[j][i] + distgraph[i][l]);
}
}
}
}
int32_t main() {
for (int i=0;i<100;i++) {
for (int j=0;j<100;j++) {
distgraph[i][j] = 2000000000;
profitgraph[i][j] = 0;
}
}
cin >> n >> m >> k;
for (int i=0;i<n;i++) {
for (int j=0;j<k;j++) {
cin >> goods[i][j].ff >> goods[i][j].ss;
}
}
int d1, d2, d3;
for (int i=0;i<m;i++) {
cin >> d1 >> d2 >> d3;
d1 -= 1; d2 -= 1;
distgraph[d1][d2] = d3;
}
distcalc();
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
for (int l=0;l<k;l++) {
if (goods[i][l].ff == -1 || goods[j][l].ss == -1) continue;
profitgraph[i][j] = max(profitgraph[i][j], goods[j][l].ss - goods[i][l].ff);
}
}
}
//for (int i=0;i<n;i++) {
// for (int j=0;j<n;j++) {
// cout << profitgraph[i][j] << ' ';
// } cout << '\n';
//} cout << '\n';
//for (int i=0;i<n;i++) {
// for (int j=0;j<n;j++) {
// cout << distgraph[i][j] << ' ';
// } cout << '\n';
//} cout << '\n';
int top = 1000000000, bottom = 0, mid;
while (top > bottom + 1) {
mid = (top + bottom) / 2;
if (checkans(mid)) bottom = mid;
else top = mid;
}
cout << bottom;
}
