#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], dummer[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=1;i<n;i++) dummer[i] = 1000000000000000000;
dummer[0] = 0;
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
for (int l=0;l<n;l++) {
if (dummer[l] > dummer[j] + dumbgraph[j][l]) dummer[l] = dummer[j] + dumbgraph[j][l];
}
}
}
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
for (int l=0;l<n;l++) {
if (dummer[l] > dummer[j] + dumbgraph[j][l]) 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] = 1000000000000000000;
profitgraph[i][j] = -1;
}
}
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);
}
}
}
int top = 1000000000000000000, bottom = 0, mid;
while (top > bottom + 1) {
mid = (top + bottom) / 2;
if (checkans(mid)) bottom = mid;
else top = mid;
}
cout << top;
}
