#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000002
#define INF2 1000000000005
int main(){
ll n, m, k, x, y, co;
cin>>n>>m>>k;
vector<vector<ll>> b(n + 1, vector<ll>(k + 1, -1)), s(n + 1, vector<ll>(k + 1, -1));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k; j++){
cin>>b[i][j]>>s[i][j];
}
}
vector<vector<ll>> di(n + 1, vector<ll>(n + 1, INF)), pr(n + 1, vector<ll>(n + 1, 0));
for (int i = 1; i <= m; i++){
cin>>x>>y>>co;
di[x][y] = min(di[x][y], co);
}
for (int l = 1; l <= n; l++){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
di[i][j] = min(di[i][j], di[i][l] + di[l][j]);
}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
for (int l = 1; l <= k; l++){
if (b[i][l] != -1 && s[j][l] != -1) pr[i][j] = max(pr[i][j], s[j][l] - b[i][l]);
}
}
}
ll l = 1, r = 1000000000, best = 0;
while (l <= r){
ll mid = (l + r) / 2;
vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, INF2));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (di[i][j] != INF) dp[i][j] = min(mid * di[i][j] - pr[i][j], dp[i][j]);
}
}
for (int z = 1; z <= n; z++){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
dp[i][j] = min(dp[i][j], dp[i][z] + dp[z][j]);
}
}
}
bool can = 0;
for (int i = 1; i <= n; i++){
if (dp[i][i] <= 0) can = 1;
}
if (can == 1){
best = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
cout<<best;
}
