#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define OR |
typedef long long ll ;
const ll ooo = 1e14 ;
const ll oo = 2e9 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7 ;
const int N = 10000010 ;
ll b[101][1010] , s[101][1010] , d[101][101] , pro[101][101];
ll ans[101][101];
int n , m , k ;
bool cn(ll md){
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= n ; ++j) ans[i][j] = md * d[i][j] - pro[i][j] ;
for(int x = 1 ; x <= n ; ++x)
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= n ; ++j){
ans[i][j] = min(ans[i][j] , ans[i][x] + ans[x][j]);
}
for(int i = 1 ; i <= n; ++i)
if(ans[i][i] <= 0) return 1;
return 0 ;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("input" , "r" , stdin );
// freopen("output" , "w" , stdout );
// #endif
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; ++i)
for(int j = 0 ; j < k ; ++j){
cin >> b[i][j] >> s[i][j];
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) d[i][j] = oo;
for(int i = 0 ; i < m ; ++i){
int x , y , z;
cin >> x >> y >> z;
d[x][y] = z;
}
for(int x = 1 ; x <= n ; ++x)
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= n ; ++j){
d[i][j] = min(d[i][j] , d[i][x] + d[x][j]);
}
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= n ; ++j){
if(i != j && d[i][j] != oo)
for(int x = 0 ; x < k ; ++x){
if(b[i][x] > 0 && s[j][x] > 0) pro[i][j] = max(pro[i][j] , s[j][x] - b[i][x]);
}
}
ll lo = 0 , hi = oo , best = 0;
while(lo <= hi){
ll md = (lo + hi) / 2;
if(cn(md)) lo = md + 1 , best = md ;
else hi = md - 1;
}
cout << best << endl;
}
