#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 i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= n ; ++j){
ans[i][i] = min(ans[i][i] , ans[i][j] + ans[j][i]);
}
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 i = 1 ; i <= n ;++i)
for(int j = 1 ; j <= n ;++j)
for(int x = 1 ; x <= n ;++x){
d[i][j] = min(d[i][j] , d[i][x] + d[x][j]);
}
for(int i = 2 ; i <= n ; ++i)
for(int j = 0 ; j < k ; ++j){
if(b[1][j] > 0 && s[i][j] > 0) pro[1][i] = max(pro[1][i] , s[i][j] - b[1][j]);
}
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;
}
