///
/// ♪ Pizza mozzarella rella rella rella... ♪
///
#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef __int128 ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;
const int N = 103, K = 1003;
const ll inf = 1e18+10;
int n, m, k;
ll A1[N][N], A2[N][N], A3[N][N];
long long S[N][K], B[N][K];
int main()
{
FAST;
cin >> n >> m >> k;
Loop(i,0,n) Loop(j,0,k) cin >> B[i][j] >> S[i][j];
Loop(i,0,n) Loop(j,0,n) A1[i][j] = inf;
Loop(i,0,n) A1[i][i] = 0;
Loop(i,0,m)
{
int v, u, w;
cin >> v >> u >> w;
--v; --u;
A1[v][u] = w;
}
Loop(k,0,n) Loop(i,0,n) Loop(j,0,n)
A1[i][j] = min(A1[i][j], A1[i][k]+A1[k][j]);
Loop(i,0,n) Loop(j,0,n) Loop(z,0,k)
if(~S[j][z] && ~B[i][z]) A2[i][j] = max(A2[i][j], (ll)S[j][z]-B[i][z]);
//Loop(i,0,n) {Loop(j,0,n) cout << (long long)A2[i][j] << ' '; cout << '\n';}
ll l = 0, r = 1e9+10;
while(l<r)
{
ll m = (l+r+1)/2;
Loop(i,0,n) Loop(j,0,n) A3[i][j] = i==j?0:1000*(A2[i][j]-m*A1[i][j])+1;
//Loop(i,0,n) {Loop(j,0,n) cout << (long long)A3[i][j] << ' '; cout << '\n';}
Loop(k,0,n) Loop(i,0,n) Loop(j,0,n)
A3[i][j] = max(A3[i][j], A3[i][k]+A3[k][j]);
bool flg=0;
Loop(i,0,n) flg |= A3[i][i];
//Loop(i,0,n) cout << (long long)A3[i][i] << ' ';
if(flg) l = m;
else r = m-1;
}
cout << (long long)l << '\n';
}
