#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define bg __int128
typedef pair<ll,ll> pii;
typedef pair<ll,pii> pip;
#define f first
#define s second
#define pb push_back
const ll L=110, L2=1010;
bg inf = 1;
const ll I=1e9+10;
int n,m,k;
ll S[L][L2],B[L][L2];
int bst[L][L];
vector<pip> edge,E;
bg dis[L][L];
bg D[L];
bool solve(ll x,int sr){
if(x == 0)
return 0;
edge.clear();
for(auto e:E){
edge.pb(e);
edge.back().f *= x;
}
for(int u=1;u<=n;u++){
for(int v=1;v<=n;v++){
if(bst[u][v] and dis[u][v] < I){
ll w = x*dis[u][v] - (S[v][bst[u][v]]-B[u][bst[u][v]]);
//cout<<u<<" -- "<<w<<" --> "<<v<<" "<<endl;
edge.pb(pip(w,pii(u,v)));
}
}
}
for(int i=1;i<=n;i++){
D[i] = inf;
}
D[sr] = 0;
for(int i=1;i<=n+1;i++){
for(auto e:edge){
D[e.s.s] = min(D[e.s.s], D[e.s.f] + e.f);
}
}
/*
cout<<"D: ";
for(int i=1;i<=n;i++){
cout<<D[i]<<" ";
}
cout<<endl;
*/
bool ok = 1;
for(auto e:edge){
ok = ok and (D[e.s.s] <= D[e.s.f]+e.f);
}
return !ok;
}
int main(){
for(int i=1;i<=21;i++){
inf *= 10;
}
//ifstream cin ("in.in");
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
cin>>B[i][j]>>S[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j] = I;
}
dis[i][i] = 0;
}
for(int i=1;i<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
E.pb(pip(w,pii(u,v)));
dis[u][v] = w;
}
for(int w=1;w<=n;w++){
for(int u=1;u<=n;u++){
for(int v=1;v<=n;v++){
dis[u][v] = min(dis[u][v], dis[u][w] + dis[w][v]);
}
}
}
for(int u=1;u<=n;u++){
for(int v=1;v<=n;v++){
if(u == v)
continue;
pii mx = pii(-1e9+10,0);
for(int i=1;i<=k;i++){
if(S[v][i] != -1 and B[u][i] != -1){
mx = max(mx,pii(S[v][i]-B[u][i],i));
}
}
bst[u][v] = mx.s;
}
}
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<"dis["<<i<<"]["<<j<<"]: "<<dis[i][j]<<endl;
}
}
cout<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<"bst["<<i<<"]["<<j<<"]: "<<bst[i][j]<<endl;
}
}
*/
ll l=0,r=I;
while(r-l > 1){
ll mid = (l+r)/2;
if(solve(mid,1))
l = mid;
else
r = mid;
}
for(int i=1;i<=n;i++){
solve(r,i);
for(int j=1;j<=n;j++){
dis[i][j] = D[j];
}
}
bool ok = 0;
for(auto e:edge){
ok = ok or (dis[e.s.s][e.s.f] == -e.f);
}
cout<<l+ok<<endl;
}
