#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
//#include "shoes.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 101;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 35;
const double eps = 0.00000000000001;
double d[NMAX];
struct Edges {
ll a, b;
double c;
};
vector <Edges> v;
ll dist[NMAX][NMAX];
ll profit[NMAX][NMAX];
ll n, m, k;
ll b[NMAX][1001], s[NMAX][1001];
bool OK(double r) {
v.clear();
for(ll i = 1; i <= n; i++) {
d[i] = INF;
for(ll j = 1; j <= n; j++) {
if(i == j)
continue;
if(dist[i][j] == INF)
continue;
v.push_back({i, j, r * dist[i][j] - profit[i][j]});
}
}
d[1] = 0;
ll ok = 1;
for(ll i = 1; i < n; i++) {
ok = 0;
for(auto x : v) {
if(d[x.a] == INF)
continue;
if(d[x.a] + x.c < d[x.b]){
d[x.b] = d[x.a] + x.c;
ok = 1;
}
}
}
return ok;
}
int main() {
ll i;
cin >> n >> m >> k;
for(i = 1; i <= n; i++) {
for(ll j = 1; j <= k; j++) {
cin >> b[i][j] >> s[i][j];
}
}
for(i = 1; i <= n; i++) {
for(ll j = 1; j <= n; j++) {
ll maxim = 0;
dist[i][j] = INF;
for(ll t = 1; t <= k; t++) {
if(s[j][t] != -1 && b[i][t] != -1)
maxim = max(maxim, s[j][t] - b[i][t]);
}
profit[i][j] = maxim;
}
}
for(i = 1; i <= m; i++) {
ll a, b, c;
cin >> a >> b >> c;
dist[a][b] = c;
}
for(ll t = 1; t <= n; t++) {
for(i = 1; i <= n; i++) {
for(ll j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);
}
}
}
double r = 0, pas = (1 << 30);
while(pas > eps){
if(OK(r + pas))
r += pas;
pas /= 2;
}
r += eps;
cout << (int)r;
return 0;
}
