// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 110, maxk = 1010, mod = 1e9 + 7, big = 1e9 + 10;
const ll inf = 1e14;
pii p[maxn][maxk];
ll d[maxn][maxn], dd[maxn][maxn], g[maxn][maxn];
int n;
bool floyd(ll a[][maxn]){
bool ok = 0;
for(int i = 1; i < n; i++)
if(a[i][0] + a[0][i] <= 0)
ok = 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
a[j][k] = min(a[j][k], a[j][i] + a[i][k]);
/* for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(a[i][j] + a[j][i] <= 0)
return 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if(a[i][j] > a[i][k] + a[k][j])
return 1;
*/
return ok;
return 0;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int m, k;
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++){
cin >> p[i][j].F >> p[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;
}
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
--a, --b;
d[a][b] = min(d[a][b], ll(c));
}
floyd(d);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(d[i][j] != inf){
for(int w = 0; w < k; w++){
if(p[i][w].F < p[j][w].S && p[i][w].F != -1 && p[j][w].S != -1)
dd[i][j] = max(dd[i][j], ll(p[j][w].S - p[i][w].F));
}
}
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
assert(d[i][j] == inf || d[i][j] <= big), assert(dd[i][j] <= big);
int l = 0, r = big;
while(r-l > 1){
int mid = (l+r) >> 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
g[i][j] = (d[i][j] == inf) ? (inf) : (1ll * mid * d[i][j] - dd[i][j]);
if(floyd(g))
l = mid;
else
r = mid;
}
assert(r != big);
return cout << l << endl, 0;
}
