#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define endl '\n'
#define ll long long
#define int ll
#define pii pair <int, int>
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846
const int N = 105, K = 1005;
const int mod = 1e9 + 7;
const int INF = 1e18;
int n, m, p;
int buy[N][K], sell[N][K], prof[N][N], a[N][N], dis[N][N], cur[N][N];
signed main() {
io;
cin >> n >> m >> p;
for(int i = 0; i < n; i++){
for(int j = 0; j < p; j++){
cin >> buy[i][j] >> sell[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
dis[i][j] = INF;
}
}
for(int i = 0; i < m; i++){
int x, y, z;
cin >> x >> y >> z;
x--;
y--;
a[x][y] = z;
dis[x][y] = z;
}
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(dis[i][k] < INF && dis[k][j] < INF){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < p; k++){
if(buy[i][k] != -1 && sell[j][k] != -1){
prof[i][j] = max(prof[i][j], sell[j][k] - buy[i][k]);
}
}
}
}
int l = 0, r = mod, ans = 0;
while(l <= r){
int mid = (l + r) / 2;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cur[i][j] = INF;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(dis[i][j] != INF && dis[i][j] * mid < INF) cur[i][j] = mid * dis[i][j] - prof[i][j];
}
}
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(cur[i][k] < INF && cur[k][j] < INF){
cur[i][j] = min(cur[i][j], cur[i][k] + cur[k][j]);
}
}
}
}
bool ok = false;
for(int i = 0; i < n; i++){
if(cur[i][i] <= 0) ok = true;
}
if(ok){
ans = max(ans, mid);
l = mid + 1;
}
else{
r = mid - 1;
}
}
cout << ans << endl;
}
