#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define upd(x, y) x=min(x, y)
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=20000000000000010LL;
const int mod=1000000007;
const int MAXN=110, MAXK=1010;
ll n, m, k, u, v, x, y, t, a, b, ans;
ll G[MAXN][MAXN], val[MAXN][MAXN];
ll B[MAXN][MAXK], S[MAXN][MAXK];
ll G2[MAXN][MAXN], dist[MAXN];
inline ll _mul(ll x, ll y){
if (INF/x<y+5) return INF;
return x*y;
}
bool check(ll x){
//memset(G2, 0, sizeof(G2));
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) G2[i][j]=_mul(x, G[i][j])-val[i][j];
//cerr<<"G2:\n";for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cerr<<G2[i][j]<<" \n"[j==n];cerr<<'\n';
memset(dist, 63, sizeof(dist));
dist[1]=0;
for (int shit=1; shit<=n; shit++){
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (G[i][j]<=inf){
ll d=dist[i]+G2[i][j];
if (d<dist[j]){
dist[j]=d;
if (shit==n) return 1;
}
}
}
// pas dor manfi nadarim!
for (int x=1; x<=n; x++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) upd(G2[i][j], G2[i][x]+G2[x][j]);
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (i!=j && G[i][j]<=inf && G2[j][i]+G2[i][j]<=0) return 1;
return 0;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
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];
}
memset(G, 63, sizeof(G));
for (int i=1; i<=n; i++) G[i][i]=0;
while (m--){
cin>>u>>v>>x;
upd(G[u][v], x);
}
for (int x=1; x<=n; x++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) upd(G[i][j], G[i][x]+G[x][j]);
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int x=1; x<=k; x++)
if (B[i][x]!=-1 && S[j][x]!=-1) val[i][j]=max(val[i][j], S[j][x]-B[i][x]);
//cerr<<"val:\n";for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cerr<<val[i][j]<<" \n"[j==n];cerr<<'\n';
/*
debug(check(2))
return 0;
*/
int dwn=0, up=inf;
while (up-dwn>1){
int mid=(dwn+up)>>1;
if (check(mid)) dwn=mid;
else up=mid;
}
cout<<dwn<<'\n';
return 0;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/
