#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second
const ll N = 3005;
const ll M = 1e9 + 7;
ll T, n, m, k, b[N][N], s[N][N], dis[N][N];
vector <pair<ll,ll>> v[N];
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
cin >> b[i][j] >> s[i][j];
}
}
for(int i = 1; i <= m; i++){
ll u1, u2, u3;
cin >> u1 >> u2 >> u3;
v[u1].push_back({u2,u3});
}
ll ans = 0;
for(int i = 1; i <= k; i++){
ans += max(0LL,s[1][i]-b[1][i]);
}
for(int i = 1; i <= n; i++){
priority_queue <pair<ll,ll>> q;
for(int j = 1; j <= n; j++) dis[i][j] = 1e9;
dis[i][i] = 0;
q.push({0,i});
while(!q.empty()){
ll w = q.top().ff, x = q.top().ss;
w *= (-1);
q.pop();
if(dis[i][x] != w) continue;
for(auto [w1,j] : v[x]){
if(dis[i][j] > dis[i][x] + w1){
dis[i][j] = dis[i][x] + w1;
q.push({-dis[i][j],j});
}
}
}
}
ll mn = 1e9;
for(int i = 2; i <= n; i++){
ll a1 = dis[i][1];
a1 += dis[1][i];
mn = min(mn, a1);
}
if(mn == 1e9 or mn == 0){
cout << 0;
}
else {
ans /= mn;
cout << ans;
}
return 0;
}
