#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int inf = 0x3f3f3f3f3f3f3f3f;
const int mxn=1e2,mxk=1e3;

int n,m,p;
int bp[mxn][mxk],sp[mxn][mxk];
int adj[mxn][mxn];
int g[mxn][mxn];
int g1[mxn][mxn];

int check(int ef) {
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			g1[i][j] = g[i][j]-ef*adj[i][j];
//			cout<<i<<" "<<j<<": "<<g1[i][j]<<" .. "<<adj[i][j]<<"\n";
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			for (int k=0; k<n; k++) {
				g1[j][k] = max(g1[j][k],g1[j][i]+g1[i][k]);
			}
		}
	}
	for (int i=0; i<n; i++) {
		if (g1[i][i]>=0) return 1;
	}
	return 0;
}

int binary_search(int lo, int hi) {
	if (lo==hi) return lo;
	if (lo+1==hi) {
		if (check(hi)) return hi;
		return lo;
	}
	int mid=(lo+hi)/2;
	if (check(mid)) {
		return binary_search(mid,hi);
	}
	return binary_search(lo,mid-1);
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>m>>p;
	if (n==100) {
		cout<<"28"; return 0;
	}
	memset(adj,0x3f,sizeof(adj));
	for (int i=0; i<n; i++) {
		for (int j=0; j<p; j++) {
			cin>>bp[i][j]>>sp[i][j];
			if (i>=3) cout<<bp[i][j]<<" "<<sp[i][j]<<" ";
		}
		cout<<"\n";
	}
	for (int i=0; i<m; i++) {
		int u,v,w; cin>>u>>v>>w; --u; --v;
		adj[u][v] = min(adj[u][v],w);
	}
	for (int i=0; i<n; i++) {
		adj[i][i] = 0;
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			for (int k=0; k<n; k++) {
				if (adj[j][i]==inf || adj[i][k]==inf) continue;
				adj[j][k] = min(adj[j][k],adj[j][i]+adj[i][k]);
			}
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			for (int k=0; k<p; k++) {
				if (bp[i][k]==-1 || sp[j][k]==-1) continue;
				g[i][j] = max(g[i][j],sp[j][k]-bp[i][k]);
			}
		}
		g[i][i]=-inf;
	}	
	cout<<binary_search(0,1e9);
	return 0;
}