#include <bits/stdc++.h>
#define int long long
int profit[110][110];
int dist[110][110];
int temp[110][110];
int buy[110][1010];
int sell[110][1010];
bool pos(int req,int n){
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)temp[i][j]=req*dist[i][j]-profit[i][j];
for(int mid=1;mid<=n;mid++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)temp[i][j]=std::min(temp[i][j],(temp[i][mid]+temp[mid][j])),temp[i][j]=std::max(temp[i][j],(int)-1e18);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(temp[i][j]+temp[j][i]<=0)return true;
return false;
}
signed main() {
int n,m,k;
std::cin >> n >> m >>k;
for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)std::cin >> buy[i][j] >> sell[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
dist[i][j]=1e9;
for(int c=1;c<=k;c++)if(buy[i][c]!=-1&&sell[j][c]!=-1)profit[i][j]=std::max(profit[i][j],sell[j][c]-buy[i][c]);
}
for(int i=1;i<=m;i++){
int f,t,w;
std::cin >> f >> t >> w;
dist[f][t]=w;
}
for(int mid=1;mid<=n;mid++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j]=std::min(dist[i][j],dist[i][mid]+dist[mid][j]);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++)
// std::cout << dist[i][j] << '/' << profit[i][j] << ' ';
// std::cout << '\n';
// }
int l=0,r=1e9;
while(l<r){
int mid=(l+r+1)/2;
if(pos(mid,n))l=mid;
else r=mid-1;
}
std::cout << l;
}
