// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;
const int maxp = 1100;
const int maxn = 150;
int n, m, p;
ll dist[maxn][maxn];
ll se[maxn][maxp], bu[maxn][maxp]; //sell at i, buy at i
ll val[maxn][maxn];
bool check(ll x){
vector<vector<ll>> dp(maxn, vector<ll> (maxn, -INF));
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
if(i != j){
dp[i][j] = val[i][j] - x * dist[i][j];
}
}
}
for(int k=1; k<=n; ++k){
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
if(dp[i][k] != -INF && dp[k][j] != -INF){
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
}
for(int i=1; i<=n; ++i){
if(dp[i][i] >= 0) return 1;
}
return 0;
}
void solve(){
cin >> n >> m >> p;
for(int i=1; i<=n; ++i){
for(int j=1; j<=p; ++j){
cin >> bu[i][j] >> se[i][j];
}
}
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
if(i != j) dist[i][j] = INF;
for(int i=1; i<=m; ++i){
int a, b, w;cin >> a >> b >> w;
dist[a][b] = min(dist[a][b], (ll)w);
}
for(int k=1; k<=n; ++k){
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
if(dist[i][k] != INF && dist[k][j] != INF){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
for(int k=1; k<=p; ++k){
if(bu[i][k] != -1 && se[j][k] != -1){
val[i][j] = max(val[i][j], se[j][k] - bu[i][k]);
}
}
}
}
//ok
int lo = 0, res = 0, hi = INF;
while(hi >= lo){
int mid = (lo + hi) >> 1;
if(check(mid)){
lo = mid + 1;
res = mid;
}
else hi = mid - 1;
}
cout << res << '\n';
}
signed main(){
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
