#include<bits/stdc++.h>
using namespace std;
const long long maxn=102,maxm=9905,maxk=1001;
long long inf=1e9+10;
long long dis[maxn][maxn],cm[maxn][maxn],b[maxn][maxk],s[maxn][maxk];
long long n,m,k;
void aval(){
for(long long i=0;i<n;i++){
for(long long j=0;j<n;j++){
for(long long h=0;h<k;h++){
if(b[i][h]==-1||s[j][h]==-1){
continue;
}
cm[i][j]=max(cm[i][j],s[j][h]-b[i][h]);
}
}
}
for(long long h=0;h<n;h++){
for(long long i=0;i<n;i++){
for(long long j=0;j<n;j++){
dis[i][j]=min(dis[i][j],dis[i][h]+dis[h][j]);
}
}
}
}
bool check(long long mid){
vector<vector<long long>>fake(maxn,vector<long long>(maxn));
for(long long i=0;i<n;i++){
for(long long j=0;j<n;j++){
if(dis[i][j]>=inf){
fake[i][j]=-inf;
}
else{
fake[i][j]=cm[i][j]-mid*dis[i][j];
}
}
}
for(long long h=0;h<n;h++){
for(long long i=0;i<n;i++){
for(long long j=0;j<n;j++){
if(fake[i][h]>=inf||fake[h][j]>=inf){
continue;
}
fake[i][j]=max(fake[i][j],fake[i][h]+fake[h][j]);
}
}
}
for(long long i=0;i<n;i++){
// if(mid==2){
// cout<<fake[i][i]<<endl;
// }
if(fake[i][i]>=0){
return 1;
}
}
return 0;
}
int main(){
cin>>n>>m>>k;
for(long long i=0;i<n;i++){
for(long long j=0;j<k;j++){
cin>>b[i][j]>>s[i][j];
}
}
for(long long i=0;i<maxn;i++){
for(long long j=0;j<maxn;j++){
dis[i][j]=inf;
}
}
for(long long i=0;i<m;i++){
long long u,v,w;
cin>>u>>v>>w;
u--;
v--;
dis[u][v]=min(w,dis[u][v]);
}
// cout<<s[0][1]<<" "<<b[2][1]<<endl;
aval();
// cout<<dis[0][2]<<" "<<dis[2][0]<<" "<<cm[0][2]<<" "<<cm[2][0]<<endl;
long long low=0,high=1e9+20,mid;
while(high-low>1){
mid=(high+low)>>1;
if(check(mid)){
low=mid;
}
else{
high=mid;
}
}
cout<<low<<endl;
}
