#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 = 305;
const ll M = 1e9 + 7;
int T, n, m, k, b[N][N*10], s[N][N*10], dis[N][N];
vector <pair<int,int>> 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++){
int u1, u2, u3;
cin >> u1 >> u2 >> u3;
v[u1].push_back({u2,u3});
}
int ans = 0;
for(int i = 1; i <= k; i++){
ans += max(0,s[1][i]-b[1][i]);
}
for(int i = 1; i <= n; i++){
priority_queue <pair<int,int>> q;
for(int j = 1; j <= n; j++) dis[i][j] = 1e9;
dis[i][i] = 0;
q.push({0,i});
while(!q.empty()){
int 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});
}
}
}
}
int mn = 1e9;
for(int i = 2; i <= n; i++){
mn = min(mn, dis[i][1] + dis[1][i]);
}
if(mn == 1e9) cout << 0;
else cout << (ans/mn);
return 0;
}
