#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
const int lmt=1e3+2,lmt2=1e2+2;
const ll inf=2e9;
int n,m,k;
ll b[lmt2][lmt],s[lmt2][lmt],dis[lmt2][lmt2],ok[lmt2][lmt2],lob[lmt2][lmt2];
int main(){
fastio;
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]=inf;
}
for(int i=1;i<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
dis[u][v]=min(dis[u][v],w);
}
for(int l=1;l<=n;l++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]>dis[i][l]+dis[l][j]){
dis[i][j]=dis[i][l]+dis[l][j];
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]==inf){
lob[i][j]=-inf;
continue;
}
for(int item=1;item<=k;item++){
if(s[j][item]==-1 || b[i][item]==-1) continue;
lob[i][j]=max(lob[i][j],s[j][item]-b[i][item]);
}
}
}
ll lo=0,hi=inf;
while(hi-lo>1){
ll mid=(lo+hi)/2;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]==inf) ok[i][j]=-inf;
else ok[i][j]=lob[i][j]-mid*dis[i][j];
}
}
for(int l=1;l<=n;l++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][l]==inf || dis[j][l]==inf) continue;
ok[i][j]=max(ok[i][j],ok[i][l]+ok[l][j]);
}
}
}
bool on=0;
for(int i=1;i<=n;i++){
if(ok[i][i]>=0){
on=1;
break;
}
}
if(on) lo=mid;
else hi=mid-1;
}
cout<<lo<<endl;
}
