#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
const ll NINF = -1'000'000'000'000'000;
vector<ll> dijkstra(int N, int start, vector<vector<pil>> (&roads))
{
//return a COST array, i.e. all values are NEGATIVE/NONPOSITIVE
priority_queue<pli, vector<pli>, greater<pli>> pq;
vector<ll> dist(N, 1);
pq.push({0, start});
while (!pq.empty())
{
pli nex = pq.top(); pq.pop();
ll leng = nex.first;
int node = nex.second;
if (dist[node] == 1)
{
dist[node] = leng;
for (pil edge: roads[node])
{
int neigh = edge.first;
ll cos = edge.second;
pq.push({leng-cos, neigh});
}
}
}
return dist;
}
vector<vector<int>> all_scc(int N, vector<vector<ll>> (&shortest_paths))
{
vector<bool> done(N, 0);
vector<vector<int>> ans;
for (int i=0; i<N; i++)
if (done[i] == 0)
{
vector<int> one_scc;
for (int j=i; j<N; j++)
{
if ((shortest_paths[i][j]!=1ll) and (shortest_paths[j][i]!=1ll))
{
done[j] = 1;
one_scc.push_back(j);
}
else
{
shortest_paths[i][j] = 1;
shortest_paths[j][i] = 1;
}
}
ans.push_back(one_scc);
}
return ans;
}
bool cycle_detector(int N, vector<vector<int>> (&edges))
{
vector<int> pointing_to(N, 0);
for (vector<int> edgelist: edges)
for (int j: edgelist)
{
pointing_to[j]++;
//cout << j << ' ';
}
queue<int> bye_bye;
for (int i=0; i<N; i++)
if (pointing_to[i] == 0)
bye_bye.push(i);
while (!bye_bye.empty())
{
int i = bye_bye.front();
bye_bye.pop();
for (int j: edges[i])
{
pointing_to[j]--;
if (pointing_to[j]==0)
bye_bye.push(j);
}
}
for (int i=0; i<N; i++)
if (pointing_to[i] > 0)
return 1;
return 0;
}
bool bellman_ford(int N, vector<vector<ll>> (&profit), vector<vector<ll>> (&shortest_paths), vector<vector<int>> (&sccs), ll efficiency)
{
vector<vector<int>> best_to_precede(N);
for (vector<int> scc: sccs)
{
int i = scc[0];
vector<ll> earnings(N, NINF);
earnings[i] = 0;
int rounds = scc.size()+1;
bool improve = 0;
for (int round = 0; round<rounds; round++)
{
improve = 0;
for (int j: scc)
for (int k: scc)
{
if (j!=k)
{
ll new_earnings = earnings[k] + profit[j][k] + efficiency*shortest_paths[j][k];
if (earnings[j] <= new_earnings)
{
if (earnings[j] < new_earnings)
{
earnings[j] = new_earnings;
improve = 1;
best_to_precede[j] = {k};
}
else
{
best_to_precede[j].push_back(k);
}
}
}
}
}
if (improve)
return 1;
}
return cycle_detector(N, best_to_precede);
}
int main()
{
int N, M, K;
cin >> N >> M >> K;
vector<vector<pll>> goods(N, vector<pll> (K));
for (int i=0; i<N; i++)
for (int j=0; j<K; j++)
{
ll b, s;
cin >> b >> s;
goods[i][j] = {b, s};
}
vector<vector<pil>> roads(N);
for (int i=0; i<M; i++)
{
int V, W; ll T;
cin >> V >> W >> T;
V--; W--;
roads[V].push_back({W, T});
}
vector<vector<ll>> shortest_paths(N);
for (int i=0; i<N; i++)
shortest_paths[i] = dijkstra(N, i, roads);
vector<vector<ll>> profit(N, vector<ll> (N, 0));
for (int i=0; i<N; i++)
for (int j=0; j<N; j++)
{
ll bes = 0;
for (int k=0; k<K; k++)
{
if ((goods[i][k].first != -1ll) and (goods[j][k].second !=-1ll))
bes = max(bes, goods[j][k].second - goods[i][k].first);
}
profit[i][j] = bes;
}
vector<vector<int>> sccs = all_scc(N, shortest_paths);
ll lo = 0;
ll hi = 1'000'000'001;
while (lo!=hi)
{
ll mid = (lo+hi+1)/2;
if (bellman_ford(N, profit, shortest_paths, sccs, mid))
lo = mid;
else
hi = mid-1;
}
cout << lo << '\n';
}
