#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll INF = 1'000'000'001LL;
// const ll INF = 100;
int main()
{
int N, M, K;
cin >> N >> M >> K;
vvll B(1+N, vll(1+K, INF));
vvll S(1+N, vll(1+K, 0));
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= K; j++)
{
ll b, s;
cin >> b >> s;
if(b != -1) B[i][j] = b;
if(s != -1) S[i][j] = s;
}
}
vvll dist(1+N, vll(1+N, INF));
for(int i = 1; i <= N; i++) dist[i][i] = 0;
for(int e = 1; e <= M; e++)
{
int V, W;
ll T;
cin >> V >> W >> T;
dist[V][W] = min(dist[V][W], T);
}
for(int k = 1; k <= N; k++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
vvll profit(1+N, vll(1+N, 0));
for(int u = 1; u <= N; u++)
for(int v = 1; v <= N; v++)
for(int j = 1; j <= K; j++)
profit[u][v] = max(profit[u][v], S[v][j] - B[u][j]);
// for(int u = 1; u <= N; u++) for(int v = 1; v <= N; v++) cerr << u << " -> " << v << " : " << dist[u][v] << ' ' << profit[u][v] << '\n';
ll lo = 0, hi = INF;
while(lo != hi)
{
// cerr << "\n\n\n\n searching in " << lo << ' ' << hi << '\n';
ll aim = (lo+hi)/2 + 1;
// cerr << "aim = " << aim << '\n';
vvll nw(1+N, vll(1+N));
for(int u = 1; u <= N; u++)
for(int v = 1; v <= N; v++)
nw[u][v] = profit[u][v] - aim*dist[u][v];
for(int k = 1; k <= N; k++)
for(int u = 1; u <= N; u++)
for(int v = 1; v <= N; v++)
nw[u][v] = max(nw[u][v], nw[u][k] + nw[k][v]);
// for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) cerr << i << " -> " << j << " : " << nw[i][j] << '\n';
bool works = 0;
for(int u = 1; u <= N; u++)
{
for(int v = 1; v <= N; v++)
{
if(u == v) continue;
works |= ((nw[u][v] + nw[v][u]) >= 0);
}
}
if(works)
lo = aim;
else
hi = aim-1;
}
cout << lo << '\n';
}
