#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int INF = (1LL<<61LL)-1LL;
int n, m, k;
struct Price{
int buy, sell;
Price(){
}
Price(int a, int b){
buy = a;
sell = b;
}
};
vector<vector<Price>> prices;
struct Road{
int dest, time;
Road(int a, int b){
dest = a;
time = b;
}
};
vector<vector<Road>>adj;
vector<vector<int>> best_t;
vector<vector<int>> best_p;
struct Node{
int id, prio;
Node(int a, int b){
id = a;
prio = b;
}
};
void bfs(int source){
vector<int> vis(n, INF);
vis[source] = 0;
auto cmp = [&](Node a, Node b){
return a.prio<b.prio;
};
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);
pq.push(Node(source, 0));
while(pq.size()>0){
auto cur = pq.top();
pq.pop();
if(vis[cur.id] >= cur.prio){
for(auto next: adj[cur.id]){
Node ev = Node(next.dest, cur.prio + next.time);
if(ev.prio<vis[next.dest]){
pq.push(ev);
vis[next.dest] = ev.prio;
}
}
}
}
for(int i = 0; i<n; i++){
best_t[source][i] = vis[i];
}
}
bool pos_loop(int rate){
auto cmp = [&](pii a, pii b){
if(a.first!=b.first){
return a.first>b.first;
}
return a.second>b.second;
};
vector<pii> best_s(n,pii(0, 0));
bool improve = true;
for(int step = 0; step<2*n+42; step++){
improve = false;
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(i!=j && best_t[i][j]!=INF){
pii c = pii(best_s[i].first + best_p[i][j] - rate *best_t[i][j], best_s[i].second+1);
if(cmp(c,best_s[j])){
improve = true;
best_s[j]= c;
}
}
}
}
}
if(improve){
return true;
}
return false;
}
signed main(){
cin>>n>>m>>k;
prices.resize(n, vector<Price> (k));
for(int i = 0; i<n; i++){
for(int e = 0; e<k; e++){
cin>>prices[i][e].buy>>prices[i][e].sell;
if(prices[i][e].buy==-1){
prices[i][e].buy = INF;
}
if(prices[i][e].sell==-1){
prices[i][e].sell=-INF;
}
}
}
adj.resize(n);
best_t.resize(n, vector<int> (n));
for(int i =0; i<m; i++){
int a, b, t;
cin>>a>>b>>t;
a--;b--;
adj[a].push_back(Road(b, t));
//cout<<"road "<<a<<" "<<b<<" "<<t<<endl;
}
for(int i = 0; i<n; i++){
bfs(i);
}
//cout<<"best_t"<<endl;
for(int i =0; i<n; i++){
for(int j = 0; j<n; j++){
//cout<<best_t[i][j]<<" ";
}
//cout<<endl;
}
best_p.resize(n, vector<int> (n, 0));
for(int i= 0; i<n; i++){
for(int j = 0; j<n; j++){
for(int p = 0; p<k; p++){
best_p[i][j] = max(best_p[i][j], prices[j][p].sell - prices[i][p].buy);
}
}
}
int res= 0;
for(int step = (1LL<<30LL); step>=1; step/=2){
if(pos_loop(res+step)){
res+=step;
}
}
cout<<res<<endl;
}
