#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
pair<int,int> dist[101][101];
int buy[101][1001];
int sell[101][1001];
int n;
bool check(int x){
vector<vector<int>> adj(n+1,vector<int>(n+1));
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
adj[i][j] = x*dist[i][j].first - dist[i][j].second;
}
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
}
for(int i=1;i<=n;i++)if(adj[i][i]<=0)return true;
return false;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m,l;
cin >> n >> m >> l;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j].first=INF;
// for(int i=1;i<=n;i++)dist[i][i].first=0;
for(int i=1;i<=n;i++)for(int j=1;j<=l;j++)cin>>buy[i][j]>>sell[i][j];
for(int i=1;i<=m;i++){
int u,v,t;cin>>u>>v>>t;
dist[u][v].first = t;
}
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
dist[i][j].first = min(dist[i][j].first,dist[i][k].first+dist[k][j].first);
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
for(int item=1;item<=l;item++){
if(buy[i][item]==-1 or sell[j][item]==-1)continue;
dist[i][j].second = max(dist[i][j].second,sell[j][item]-buy[i][item]);
}
}
int ans = 0;
for(int jump=536870912ll;jump;jump/=2){
if(check(ans+jump))ans+=jump;
}
cout << ans << '\n';
}
