#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,k;
cin >> n >> m >> k;
int graph[n][n];
for(int i = 0;i<n;i++){
fill(graph[i],graph[i]+n,inf);
}
int b[n][k];
int s[n][k];
for(int i = 0;i<n;i++){
for(int j = 0;j<k;j++){
cin >> b[i][j] >> s[i][j];
}
}
for(int i = 0;i<m;i++){
int a,b,t;
cin >> a >> b >> t;
a--;b--;
graph[a][b]=t;
}
for(int k = 0;k<n;k++){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
}
}
}
int prof[n][n];
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
prof[i][j]=0;
for(int o = 0;o<k;o++){
if(s[j][o]==-1||b[i][o]==-1)
continue;
prof[i][j]=max(prof[i][j],s[j][o]-b[i][o]);
}
}
}
int lo = 0;
int hi = inf;
int temp[n][n];
while(lo<hi){
int mid = (lo+hi+1)/2;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
temp[i][j]=mid*min(graph[i][j],inf/mid)-prof[i][j];
}
}
for(int k = 0;k<n;k++){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
temp[i][j]=min(temp[i][j],temp[i][k]+temp[k][j]);
}
}
}
bool wor = 0;
for(int i = 0;i<n;i++){
if(temp[i][i]<=0){
wor=1;
}
}
if(wor){
lo=mid;
}
else{
hi=mid-1;
}
}
cout << lo;
return 0;
}
