/*
* author : Apiram
* created: 29.04.2023 02:41:46
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m,k;cin>>n>>m>>k;
vector<vector<long long>>b(n),s(n);
for (int i = 0;i<n;++i){
for (int j = 0;j<k;++j){
long long x,y;cin>>x>>y;
b[i].push_back(x);
s[i].push_back(y);
}
}
vector<vector<long long>>dist(n,vector<long long>(n,1e16));
for (int i = 0;i<m;++i){
long long x,y,cost;
cin>>x>>y>>cost;
--x;--y;
dist[x][y] = min(dist[x][y],cost);
}
for (int i = 0;i<n;++i){
for (int j = 0;j<n;++j){
for (int p = 0;p<n;++p){
dist[j][p] = min(dist[j][p],dist[j][i] + dist[i][p]);
}
}
}
long long ans = 0;
long long left = 0,right = 1e10;
while(left<=right){
long long mid = (left + right)>>1;
//profit / time >= mid
//profit >= mid * time
//-profit + mid * time <= 0
vector<vector<long long>>cost(n,vector<long long>(n,1e16));
for (int i = 0;i<n;++i){
for (int j = 0;j<n;++j){
if (dist[i][j] == 1e16)continue;
for (int p = 0;p<k;++p){
if (b[i][p] == -1 || s[j][p] == -1){
cost[i][j] = mid * dist[i][j];
}
else{
cost[i][j] = min(cost[i][j],mid * dist[i][j] - (s[j][p] - b[i][p]));
}
}
}
}
for (int i = 0;i<n;++i){
for (int j = 0;j<n;++j){
for (int p = 0;p<n;++p){
cost[j][p] = min(cost[j][i] + cost[i][p],cost[j][p]);
}
}
}
bool ok = false;
for (int i = 0;i<n;++i){
if (cost[i][i] <= 0){
ok = true;
}
}
if (ok){
left = mid + 1;
ans = mid;
}
else{
right = mid - 1;
}
}
cout<<ans<<'\n';
return 0;
}
