#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e2 + 7;
constexpr ll oo = 8e18;
ll dist[MAXN][MAXN];
ll profit[MAXN][MAXN];
ll cycle[MAXN][MAXN];
pair<ll, ll> market[MAXN][1007];
int n, m, k;
void computeDist(){
for(int l = 1; l <= n; l++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][l] != oo && dist[l][j] != oo)
dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);
}
void computeProfit(){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
profit[i][j] = -oo;
for(int l = 1; l <= k; l++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(market[i][l].first != -1 && market[j][l].second != -1 && dist[i][j] != oo)
profit[i][j] = max(profit[i][j], market[j][l].second - market[i][l].first);
}
void prepare(ll x){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][j] != oo)
cycle[i][j] = (dist[i][j] * x) - profit[i][j];
}
bool check(ll x){
prepare(x);
for(int l = 1; l <= n; l++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cycle[i][j] = min(cycle[i][j], cycle[i][l] + cycle[l][j]);
for(int l = 1; l <= n; l++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(cycle[i][j] > cycle[i][l] + cycle[l][j]) return true;
return false;
}
ll BS(){
ll l = 0, r = 1e9, mid;
while(l < r){
mid = (l+r)/2;
if(check(mid)) l = mid + 1;
else r = mid;
}
if(check(l)) return l;
return --l;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= k; j++)
cin >> market[i][j].first >> market[i][j].second;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j) dist[i][j] = oo;
for(int i = 1; i <= m; i++){
int u, v;
ll t;
cin >> u >> v >> t;
dist[u][v] = min(dist[u][v], t);
}
computeDist();
computeProfit();
cout << BS()+1 << "\n";
}
