#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
const int INF = LLONG_MAX/2;
int n,m,k, prof[105][105], w[105][105];
vector<vector<int>> dist(105, vector<int>(105, INF));
vector<vector<pll>> dp(105, vector<pll>(105));
vector<vector<pll>> v(105);
signed main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
int a,b;cin>>a>>b;
v[i].pb({a,b});
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int z=0;z<k;z++){
if(v[j][z].s!=-1 and v[i][z].f != -1){
prof[i][j]=max(prof[i][j],v[j][z].s-v[i][z].f);
}
}
//~ printf("from %lld to %lld, prof %lld\n", i, j, prof[i][j]);
}
}
//~ for(int i=0;i<n;i++)dist[i][i]=0;
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;
a--,b--;
dist[a][b]=c;
}
for(int z=0;z<n;z++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dist[i][j]=min(dist[i][z]+dist[z][j], dist[i][j]);
}
}
}
int l=1, r=1e9+1;
while(l<r-1){
int m=(l+r)/2;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
w[i][j]=m*min(dist[i][j], INF/m) - prof[i][j];
}
}
//~ printf("m %lld\n",m);
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<n;j++){
//~ cout<<w[i][j]<<" ";
//~ }
//~ cout<<endl;
//~ }
for(int z=0;z<n;z++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
w[i][j]=min(w[i][z]+w[z][j], w[i][j]);
}
}
}
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<n;j++){
//~ cout<<w[i][j]<<" ";
//~ }
//~ cout<<endl;
//~ }
bool ok=false;
for(int i=0;i<n;i++)if(w[i][i]<=0)ok=true;
if(ok)l=m;
else r=m;
}
cout<<l;
}
