#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
#define l first
#define r second
const int lmt=101;
vector<pair<ll,ll>>adj[lmt];
ll b[lmt][1001],s[lmt][1001],dis[lmt][lmt],val[lmt][lmt],n,m,k,mx[lmt][lmt];
bool ok(ll x){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
val[i][j]=-2e9;
if(dis[i][j]>=2e9) continue;
val[i][j]=max(val[i][j],-dis[i][j]*x+mx[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int l=1;l<=n;l++){
if(dis[i][l]>=2e9 || dis[l][j]>=2e9) continue;
val[i][j]=max(val[i][j],val[i][l]+val[l][j]);
}
}
}
for(int i=1;i<=n;i++){
if(val[i][i]>=0) return true;
}
return false;
}
int main(){
fastio;
cin>>n>>m>>k;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++) dis[i][j]=2e9;
}
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<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
dis[u][v]=w;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int l=1;l<=n;l++){
dis[i][j]=min(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]==2e9){
mx[i][j]=-2e9;
continue;
}
for(int l=1;l<=k;l++){
if(s[j][l]==-1 || b[i][l]==-1) continue;
mx[i][j]=max(mx[i][j],s[j][l]-b[i][l]);
}
}
}
ll lo=0,hi=1e9;
while(hi-lo>1){
ll mid=(lo+hi)>>1;
if(ok(mid)) lo=mid;
else hi=mid;
}
if(ok(hi)) cout<<hi<<endl;
else cout<<lo<<endl;
return 0;
}
