#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 110;
const ll inf = 1e18;
int N,M,K;
struct Edge{
int f,t;
ll c,w;
Edge(int ff = 0,int tt = 0,ll cc = 0,ll ww = 0):f(ff),t(tt),c(cc),w(ww){};
};
vector<Edge> edges;
namespace S1{//get all pair shortest path+max profit
ll dist[mxn][mxn];
pii shop[mxn][mxn*10];
void init(){
for(auto &i:dist)for(auto &j:i)j = inf;
for(int i = 1;i<=N;i++)dist[i][i] = 0;
for(int i = 1;i<=N;i++){
for(int j = 1;j<=K;j++)cin>>shop[i][j].fs>>shop[i][j].sc;
}
for(int i = 0;i<M;i++){
int a,b,c;
cin>>a>>b>>c;
dist[a][b] = min(dist[a][b],1ll*c);
}
}
void GO(){
for(int i = 1;i<=N;i++){
for(int j = 1;j<=N;j++){
for(int k = 1;k<=N;k++){
dist[j][k] = min(dist[j][k],dist[j][i]+dist[i][k]);
}
}
}
for(int i = 1;i<=N;i++){
for(int j = 1;j<=N;j++){
if(i == j||dist[i][j]>=inf)continue;
int pr = 0;
for(int k = 1;k<=K;k++){
if(shop[i][k].fs == -1||shop[j][k].sc == -1)continue;
pr = max(pr,shop[j][k].sc-shop[i][k].fs);
}
edges.push_back(Edge(i,j,pr,dist[i][j]));
}
}
return;
}
}
namespace S2{//binary search+BF
ll dist[mxn];
int relax[mxn];
bool check(ll coef){
memset(relax,0,sizeof(relax));
memset(dist,0,sizeof(dist));
bool flag = false;
for(int i = 0;i<=N+10;i++){
for(auto &e:edges){
ll d = coef*e.w-e.c;
//cerr<<e.f<<' '<<e.t<<':'<<d<<endl;
if(dist[e.f]+d<=dist[e.t]){
relax[e.t] = max(relax[e.t],relax[e.f]+1);
dist[e.t] = dist[e.f]+d;
}
if(relax[e.f]>=N+1)flag = true;
}
}
/*
cerr<<coef<<":"<<endl;
for(int i = 1;i<=N;i++)cerr<<dist[i]<<' ';cerr<<endl;
for(int i = 1;i<=N;i++)cerr<<relax[i]<<' ';cerr<<endl;
*/
return flag;
}
void GO(){
ll l = -1,r = 1e9;
while(l != r){
ll mid = l+(r-l+1)/2;
if(check(mid))l = mid;
else r = mid-1;
}
cout<<l<<'\n';
return;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>M>>K;
S1::init();
S1::GO();
//for(auto &i:edges)cerr<<i.f<<' '<<i.t<<' '<<i.w<<' '<<i.c<<endl;
S2::GO();
}
