#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define mins(a,b) (a=min(a,b))
#define maxs(a,b) (a=max(a,b))
const int MXN = 100;
const ll INF = 1e18;
int n;
void floyd(ll d[MXN][MXN]){
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
mins(d[i][j], d[i][k]+d[k][j]);
}
int s[MXN][MXN*10], b[MXN][MXN*10];
ll dis[MXN][MXN], cash[MXN][MXN], dp[MXN][MXN];
bool chk(int x) {
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
dp[i][j] = x * min(dis[i][j], INF/x) - cash[i][j];
floyd(dp);
for(int i=0; i<n; i++)
if(dp[i][i]<=0)
return 1;
return 0;
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
int m, k;
cin >> n >> m >> k;
for(int i=0; i<n; i++) {
fill(dis[i], dis[i]+n, INF);
for(int j=0; j<k; j++) cin >> b[i][j] >> s[i][j];
}
for(int i=0, u,v,w; i<m; i++) {
cin >> u >> v >> w;
dis[u-1][v-1] = w;
}
floyd(dis);
for(int x=0; x<k; x++)
for(int i=0; i<n; i++)
if(b[i][x]!=-1)
for(int j=0; j<n; j++)
if(s[j][x]!=-1)
maxs(cash[i][j], 1ll*s[j][x] - b[i][x]);
int l=0, r=1e9+1;
while(r-l>1)
(chk(l+r>>1) ? l : r) = l+r>>1;
cout << l << '\n';
return 0;
}
