#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vect;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define pb push_back
#define f first
#define s second
const int N = 101;
const int K = 1001;
ll dist[N][N], b[N][K], s[N][K], kraw[N][N];
int checker(ll x, int n){
vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 1e18)), czy(n + 1, vector<ll>(n + 1, 0));
for(int i = 1; i <= n; i++) dp[i][i] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(dist[i][j] == 1e18) continue;
dp[i][j] = -(kraw[i][j] - x * dist[i][j]);
}
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(k == i && i == j) continue;
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
if(dp[i][j] == dp[i][k] + dp[k][j]) czy[i][j] = 1;
}
}
}
for(int i = 1; i <= n; i++){
if(czy[i][i] == 1 && dp[i][i] <= 0) return i;
}
return 0;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(j == i) continue;
dist[i][j] = 1e18;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
cin >> b[i][j] >> s[i][j];
}
}
for(int i = 0; i < m; i++){
ll u, v, w; cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w);
}
for(int x = 1; x <= n; x++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i == j) continue;
if(dist[j][i] == 1e18) continue;
for(int z = 1; z <= k; z++){
if(b[j][z] != -1 && s[i][z] != -1){
kraw[j][i] = max(kraw[j][i], s[i][z] - b[j][z]);
}
}
}
}
ll l = 0, r = 1e9;
while(l < r){
ll mid = (l + r + 1) / 2;
if(checker(mid, n)){
l = mid;
}else{
r = mid - 1;
}
}
cout << l << "\n";
return 0;
}
