#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x) cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define plii pair<ll, pii>
#define nl endl
#define tb '\t'
#define sp ' '
using namespace std;
const ll MX=250007, MOD=1e9+7, BLOCK=327, INF=1e9+7, INFF=1e18+7;
const ld ERR=1e-7, pi=3.14159265358979323846;
ll N, M, K, B[107][1007], S[107][1007], dist[107][107], dist2[107][107], profit[107][107];
bool bisa(ll x){
for(int i=0; i<=N; i++){
for(int j=0; j<=N; j++){
dist2[i][j]=-INF;
if(dist[i][j]!=INF)
dist2[i][j]=profit[i][j]-x*dist[i][j];
}
}
bool ret=0;
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
dist2[i][j]=max(dist2[i][j], dist2[i][k]+dist2[k][j]);
for(int i=1; i<=N; i++)
if(dist2[i][i]>=0)
return 1;
return 0;
}
int main(){
fastio;
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=0; i<=N; i++){
for(int j=0; j<=N; j++){
dist[i][j]=INF;
profit[i][j]=0;
}
}
for(ll u, v, w, i=0; i<M; i++){
cin >> u >> v >> w;
dist[u][v]=min(dist[u][v], w);
}
for(int k=1; k<=N; k++)
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
for(int k=1; k<=K; k++)
if(B[i][k]!=-1 && S[j][k]!=-1)
profit[i][j]=max(profit[i][j], S[j][k]-B[i][k]);
ll le=1, ri=INF, mi;
while(le<=ri){
mi=(le+ri)/2;
if(bisa(mi))
le=mi+1;
else
ri=mi-1;
}
cout << le-1 << nl;
}
