//khodaya khodet komak kon
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-O2")
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 100 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;
int n, m, K, B[N][N * 10], S[N][N * 10];
ll dis[N][N], pth[N][N], D[N];
vector<pair<int, ll>> G[N];
bool relax(int v, int u, ll w){
//cout << v << ' ' << u << ' ' << w << ' ' << D[v] << ' ' << D[u] << '\n';
if (D[u] > D[v] + w){
D[u] = D[v] + w;
return 1;
}
return 0;
}
bool isval(ll x){
for (int i = 1; i <= n; i++) G[i].clear();
fill(D + 1, D + n + 1, INF);
//cout << D[1] << ' ' << D[2] << '\n';
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (i == j) continue;
if (dis[i][j] == INF) continue;
G[i].pb({j, x * dis[i][j] - pth[i][j]});
// cout << i << ' ' << j << ' ' << x * dis[i][j] - pth[i][j] << '\n';
}
}
for (auto u:G[1]){
D[u.F] = u.S;
}
for (int i = 1; i <= n + 2; i++){
bool f = 0;
for (int j = 1; j <= n; j++){
for (auto u:G[j]){
f |= ((dis[u.F][1] != INF) && relax(j, u.F, u.S));
// if (relax(j, u.F, u.S) && i >= n + 1 && dis[u.F][1] != INF) return 1;
}
}
if (f && i == n + 2) return 1;
}
//cout << "Fuck\n";
//for (int i = 1; i <= n; i++) cout << i << ' ' << D[i] << '\n';
return (D[1] <= 0);
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> K;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= 2 * K; j++){
if (j % 2 == 1) cin >> B[i][j / 2 + 1];
else cin >> S[i][j / 2];
}
}
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dis[i][j] = INF;
for (int i =1 ; i <= m; i++){
ll v, u, T;
cin >> v >> u >> T;
dis[v][u] = min(dis[v][u], T);
}
for (int k = 1; k <= n; k++)for (int v = 1; v <= n; v++) for (int u = 1; u <= n; u++) dis[v][u] = min(dis[v][u], dis[v][k] + dis[k][u]);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (dis[i][j] == INF) continue;
for (int k = 1; k <= K; k++){
if (S[j][k] == -1 || B[i][k] == -1) continue;
pth[i][j] = max(pth[i][j], S[j][k] - B[i][k]);
}
//cout << i << ' ' << j << ' ' << pth[i][j] << '\n';
}
}
ll l = 0, r = INF;
while (r - l > 1){
ll md = (l + r) >> 1;
if (isval(md)) l = md;
else r = md;
}
cout << l;
// isval(5);
return 0;
}
