#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 4;
const long long infll = 1e18;
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
#endif // LOCAL
int N, M, K;
cin >> N >> M >> K;
vector<vector<array<int, 2>>> items(N, vector<array<int, 2>>(K)); //[buy, sell]
for(int i = 0; i < N; ++i){
for(int j = 0; j < K; ++j){
cin >> items[i][j][0] >> items[i][j][1];
}
}
vector<vector<int>> dist(N, vector<int>(N, inf));
while(M--){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
dist[u][v] = w;
}
for(int k = 0; k < N; ++k){
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
minimize(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
vector<vector<long long>> delta(N, vector<long long>(N, -infll));
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j) if(dist[i][j] != inf){
for(int k = 0; k < K; ++k) if(items[i][k][0] != -1 && items[j][k][1] != -1){
maximize(delta[i][j], - (long long)items[i][k][0] + items[j][k][1]);
}
}
}
vector<vector<long long>> f(N, vector<long long>(N, -infll));
auto check = [&](int x){
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
f[i][j] = max(0ll, delta[i][j]) - 1LL * x * dist[i][j];
}
}
for(int k = 0; k < N; ++k){
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
maximize(f[i][j], f[i][k] + f[k][j]);
}
}
}
for(int i = 0; i < N; ++i)
if(f[i][i] >= 0) return true;
return false;
};
int l = 0, r = 1e9, ans = 0;
while(l <= r){
int mid = l + r >> 1;
if(check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans << '\n';
return 0;
}
