/** I can do this all day **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
const int N = 1e2 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 1e18;
const int LOG = 22;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
int n, m, K;
ll dis[N][N], D[N][N], Mx[N][N], B[N][N], S[N][N];
void calc(int v, int u)
{
Mx[v][u] = 0;
for(int i = 1; i <= K; i ++)
{
Mx[v][u] = max(Mx[v][u], S[u][i] - B[v][i]);
}
}
bool check(ll x)
{
// printf("checking D\n");
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
if(dis[i][j] >= inf) D[i][j] = -inf;
else D[i][j] = Mx[i][j] - dis[i][j] * x;
///printf("%lld ", D[i][j]);
}
///printf("\n");
}
for(int k = 1; k <= n; k ++)
{
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
D[i][j] = max(D[i][j], D[i][k] + D[k][j]);
}
}
}
for(int i = 1; i <= n; i ++)
{
if(D[i][i] >= 0) return 1;
}
return 0;
}
int main()
{
scanf("%d%d%d", &n, &m, &K);
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= K; j ++)
{
scanf("%lld%lld", &B[i][j], &S[i][j]);
if(B[i][j] == -1) B[i][j] = inf;
if(S[i][j] == -1) S[i][j] = -inf;
}
}
for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) calc(i, j), dis[i][j] = inf;
for(int i = 1; i <= m; i ++)
{
ll a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
dis[a][b] = min(dis[a][b], c);
}
for(int k = 1; k <= n; k ++)
{
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
/*printf("checking Mx\n");
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
printf("%lld ", Mx[i][j]);
}
printf("\n");
} */
ll d = 0, up = 1e16 + 10;
while(up - d > 1)
{
ll mid = (up + d) >> 1;
if(check(mid)) d = mid;
else up = mid;
}
printf("%lld", d);
return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/
