#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 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 && i != j)
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];
else cycle[i][j] = oo;
}
}
}
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++)
if(dist[i][l] != oo && dist[l][j] != oo)
cycle[i][j] = min(cycle[i][j], cycle[i][l] + cycle[l][j]);
/*
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cout << "i: " << i << " j " << j << " cycle: " << cycle[i][j] << "\n";
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)
if(cycle[i][j] > cycle[i][l] + cycle[l][j]) return true;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][j] != oo && dist[j][i] != oo && i != j)
if(cycle[i][j] + cycle[j][i] <= 0) return true;
*/
for(int i = 1; i <= n; i++)
if(cycle[i][i] <= 0) 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 max(--l, (ll)0);
}
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++)
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();
/*
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cout << "i " << i << " j " << j << " profit " << profit[i][j] << "\n";
check(1);
cout << "\n";
check(2);
cout << "\n";
check(3);
cout << "\n";
check(4);
cout << "\n";
*/
cout << BS() << "\n";
}
