#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const ll mod = 1e9 + 7;
const ll INF = 1e18;
//--------------------------------------------------------------------
const ll N = 103;
const ll K = 1003;
ll n, m, k;
vector<pa> g[N];
pa a[N][K];
ll dist[N][N], c[N][N], cost[N][N];
bool check(ll X) {
memset(dist, -0x3f, sizeof dist);
FOR(i, 1, n) {
FOR(j, 1, n) {
if(c[i][j] > INF) continue;
dist[i][j] = cost[i][j] - X * c[i][j];
// cout << i << ' ' << j << ' ' << dist[i][j] << '\n';
}
}
FOR(k, 1, n) {
FOR(u, 1, n) {
FOR(v, 1, n) {
if(dist[u][k] < -INF || dist[k][v] < -INF) continue;
dist[u][v] = max(dist[u][v], dist[u][k] + dist[k][v]);
// cout << u << ' ' << v << ' ' << dist[u][v] << '\n';
}
}
}
FOR(i, 1, n) {
if(dist[i][i] >= 0) {
return true;
}
}
return false;
}
void hbmt() {
cin >> n >> m >> k;
FOR(i, 1, n) {
FOR(j, 1, k) {
ll s, b;
cin >> b >> s;
a[i][j] = {b, s};
}
}
memset(c, 0x3f, sizeof c);
FOR(i, 1, m) {
ll u, v, w;
cin >> u >> v >> w;
c[u][v] = w;
}
FOR(i, 1, n) {
FOR(j, 1, n) {
FOR(u, 1, k) {
if(a[i][u].fi != -1 && a[j][u].se != -1) {
cost[i][j] = max(cost[i][j], a[j][u].se - a[i][u].fi);
}
}
}
}
FOR(k, 1, n) {
FOR(u, 1, n) {
FOR(v, 1, n) {
c[u][v] = min(c[u][v], c[u][k] + c[k][v]);
}
}
}
// cout << c[1][1] << '\n';
// cout << check(5) << '\n';
// return;
ll l = 1, r = 1e9;
ll res = 0;
while(l <= r) {
ll mid = l + r >> 1;
if(check(mid)) {
l = mid + 1;
res = mid;
}
else r = mid - 1;
}
cout << res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#define NAME "hbmt"
if(fopen(NAME".inp", "r")) {
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
//int t;cin>>t;while(t--)
hbmt();
return 0;
}
