#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vi vector<int>
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl
using namespace std;
const int mxn = 105, mxk = 1005;
int n,m,k,b[mxn][mxk],s[mxn][mxk],ans=0,dist[mxn][mxn],c[mxn][mxn],d[mxn][mxn]; vector<pii>adj[mxn],G[mxn];
struct Edge{int a, b, w;};
bool check_neg(){
f0r(i,n)f0r(j,n)d[i][j] = 4e18;
f0r(i,n)for(auto [b,w] : G[i])d[i][b] = min(d[i][b], w);
f0r(k,n)f0r(i,n)f0r(j,n)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
f0r(i,n)if(d[i][i] <= 0)return 1; return 0;
}
signed main(){
cin>>n>>m>>k; f0r(i,n){
f0r(j,k){int x,y; cin>>x>>y; b[i][j] = x, s[i][j] = y;}
}
f0r(i,m){
int u,v,w; cin>>u>>v>>w; u--; v--; adj[u].eb(v,w);
}
f0r(i,n)f0r(j,n)dist[i][j]=2e9;
f0r(i,n){
dist[i][i] = 0; priority_queue<pair<int,int>>q; q.push(mp(0,i)); while(!q.empty()){
int node = q.top().second; q.pop(); for(auto [u,w] : adj[node]){
if(dist[i][u] > dist[i][node] + w){
dist[i][u] = dist[i][node] + w; q.push(mp(-dist[i][u], u));
}
}
}
}
// f0r(i,n){
// f0r(j,n){
// if(dist[i][j]==2e9)cout<<-1<<' '; else cout<<dist[i][j]<<' ';
// }cout<<'\n';
// }
// FOR(i,1,n){
// int mx = 0; f0r(j,k)if(b[0][j] != -1 && s[i][j] != -1)mx = max(mx, s[i][j] - b[0][j]);
// if(dist[0][i] != 2e9 && dist[i][0] != 2e9)ans = max(ans, mx / (dist[0][i]+dist[i][0]));
// } cout<<ans;
f0r(i,n)f0r(j,n)if(i!=j){
int mx = 0; f0r(l,k){
if(b[i][l] != -1 && s[j][l] != -1)mx = max(mx, s[j][l] - b[i][l]);
} c[i][j]=mx;
}
int lo = 0, hi = 1e9 + 5; while(lo < hi){
int mid = lo + (hi - lo + 1) / 2; f0r(i,n)G[i].clear();
f0r(i,n)f0r(j,n)if(i!=j && dist[i][j] < 2e9)G[i].eb(j, mid * dist[i][j] - c[i][j]);
bool b = check_neg();
if(b)lo = mid; else hi = mid - 1;
} cout<<lo;
}
