#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"
const int maxn = 1e6 + 100;
const ll INF = (ll)1e18;
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;
int n, m, k;
ll b[110][1010];
ll s[110][1010];
ll d[110][110];
ll c[110][110];
ll a[110][110];
bool ok(ll x){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i == j) a[i][j] = -INF;
else a[i][j] = c[i][j] - d[i][j] * min(INF / d[i][j], x);
}
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
a[i][j] = max(a[i][j], a[i][k] + a[k][j]);
}
}
}
for(int i = 1; i <= n; i++){
if(a[i][i] >= 0) return 1;
}
return 0;
}
void test(){
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
cin >> b[i][j] >> s[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
d[i][j] = INF;
}
}
for(int i = 1; i <= m; i++){
int a, b, c;
cin >> a >> b >> c;
d[a][b] = c;
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int t = 1; t <= k; t++){
if(b[i][t] != -1 && s[j][t] != -1) c[i][j] = max(c[i][j], s[j][t] - b[i][t]);
}
}
}
ll ans = 0;
for(int l = 1, r = 1e9; l <= r;){
int mid = (l + r) >> 1;
if(!ok(mid)) r = mid - 1;
else l = mid + 1, ans = mid;
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; t = 1;
while(t--) test();
}
