#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define sz size
#define pii pair<ll,ll>
#define f first
#define s second
const int mxN = 100;
const int mxK = 1e3;
const ll inf = 1e18;
int n,m,k;
ll d[mxN][mxN];
ll p[mxN][mxN];
pii vals[mxN][mxK];
bool solve(ll x){
ll d2[n][n];
for (int i =0; i < n; i++) for (int j =0; j < n; j++){
if (d[i][j] == inf || d[i][j] >= inf/x) d2[i][j] = inf;
else d2[i][j] = d[i][j]*x-p[i][j];
}
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
if (d2[i][k] != inf && d2[k][j] != inf) d2[i][j] = min(d2[i][j],d2[i][k]+d2[k][j]);
}
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
if (i == j || d2[i][j] == inf || d2[j][i] == inf) continue;
if (d2[i][j] + d2[j][i] <= 0) return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> vals[i][j].f >> vals[i][j].s;
for (int i =0; i < n; i++){
for (int j =0; j < n; j++) d[i][j] = inf;
d[i][i] = 0;
}
ll v,w,t;
for (int i = 0; i < m; i++){
cin >> v >> w >> t;
v -= 1;
w -= 1;
d[v][w] = min(d[v][w],(ll)t);
}
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
if (d[i][k] != inf && d[k][j] != inf) d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
/* for (int i =0; i < n; i++){
for (int j =0; j < n; j++) cout << d[i][j] << " ";
cout << '\n';
}*/
memset(p,0,sizeof(p));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int t = 0; t < k; t++){
if (vals[i][t].f == -1 || vals[j][t].s == -1) continue;
p[i][j] = max(p[i][j],vals[j][t].s - vals[i][t].f);
}
/* for (int i =0; i < n; i++){
for (int j = 0; j < n; j++) cout << p[i][j] << " ";
cout << '\n';
}
*/
ll l = 0;
ll r = 1e9+1;
ll c;
while (r-l>1){
c = (l+r)/2;
if (solve(c)) l = c;
else r = c;
}
cout << l << "\n";
return 0;
}
