#include <bits/stdc++.h>
#define int long long
#define REP(i,a,b) for(int i = a; i<b; i++)
#define RREP(i,a,b) for(int i = a; i>b; i--)
using namespace std;
int inf = 1e18;
int n,m,k;
vector<vector<int>> adj2, p, adj;
bool check(int r){
REP(i,0,n){
REP(j,0,n){
if(i == j) adj[i][i] = 0;
adj2[i][j] = r*adj[i][j] - p[i][j];
}
}
REP(i,0,n){
REP(j,0,n){
REP(k,0,n){
adj2[j][k] = min(adj2[j][k], adj2[j][i]+adj2[i][k]);
}
}
}
bool pos = true;
REP(i,0,n){
if(adj2[i][i]<0) pos = false;
}
return !pos;
}
int search(int l, int r){
if(l == r) return l;
int mid = (l+r)/2;
if(check(mid+1)) return search(mid+1,r);
return search(l,mid);
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m>>k;
vector<vector<int>> b(n, vector<int>(k)), s(n, vector<int>(k));
adj.resize(n,vector<int>(n,inf));
p.resize(n, vector<int>(n,-inf));
adj2.resize(n,vector<int>(n));
REP(i,0,n){
REP(j,0,k){
cin>>b[i][j];
cin>>s[i][j];
}
}
REP(i,0,m){
int u,v,t;
cin>>u>>v>>t;
u--; v--;
adj[u][v] = t;
adj[v][u] = t;
}
REP(i,0,n){
REP(j,0,n){
REP(x,0,k){
if(s[j][x] != -1 && b[i][x] != -1)
p[i][j] = max(p[i][j], s[j][x] - b[i][x]);
}
}
}
REP(x,0,n){
REP(y,0,n){
REP(z,0,n){
adj[y][z] = min(adj[y][z],adj[y][x]+adj[x][z]);
}
}
}
int r = search(1,1e9);
cout<<r;
}
