#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=107,K=1007;

int bx[N][K],sx[N][K];
int d[N][N];
int C[N][N];
ll D[N][N];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    FOR(i,1,n) FOR(j,1,k) cin>>bx[i][j]>>sx[i][j];
    FOR(i,1,n) 
    {
		FOR(j,1,n)
		{
			if(i==j) continue;
			d[i][j]=inf;
			FOR(l,1,k) if(sx[j][l]!=-1&&bx[i][l]!=-1) C[i][j]=max(C[i][j],sx[j][l]-bx[i][l]);
		}
	}
    FOR(i,1,m)
    {
		int a,b,c;
		cin>>a>>b>>c;
		d[a][b]=min(d[a][b],c);
	}
	FOR(t,1,n) FOR(i,1,n) FOR(j,1,n) d[i][j]=min(d[i][j],d[i][t]+d[t][j]);
	/*ll ans=0;
	FOR(i,2,n) ans=max(ans,C[1][i]/(d[1][i]+d[i][1]));
	cout<<ans<<endl;*/
	int l=1,r=1000000000,ans=0;
	while(l<=r)
	{
		int sr=(l+r)/2;
		FOR(i,1,n)
		{
			FOR(j,1,n)
			{
				if(i==j) D[i][j]=0;
				else 
				{
					if(d[i][j]==inf) D[i][j]=-infl;
					else D[i][j]=(ll)C[i][j]-(ll)sr*(ll)d[i][j];
				}
			}
		}
		bool ok=0;
		//FOR(i,2,n) if(D[1][i]+D[i][1]>=0) ok=1;
		/*FOR(t,1,n) FOR(i,1,n) FOR(j,1,n) D[i][j]=max(D[i][j],D[i][t]+D[t][j]);*/
		FOR(i,1,n) FOR(j,1,n) if(i!=j) if(D[i][j]+D[j][i]>=0) ok=1;
		if(ok)
		{
			ans=sr;
			l=sr+1;
		}
		else r=sr-1;
	}
	cout<<ans<<endl;
	
    
    
    
    
    return 0;
}