#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
const int maxn = 102, maxk = 1e3+2, inf = 1e9+10;
ll b[maxn][maxk], s[maxn][maxk], max_ben[maxn][maxn], dis[maxn][maxn];
int N, M, K;
struct edge
{
int v, u;
};
vector<edge> edges;
void FloydWarshall()
{
for(int v = 0; v < N; v++)
dis[v][v] = 0;
for(int k = 0; k < N; k++)
{
for(int v = 0; v < N; v++)
{
for(int u = 0; u < N; u++)
{
dis[v][u] = min(dis[u][v], dis[v][k] + dis[k][u]);
}
}
}
return;
}
void CalcBen()
{
for(int v = 0; v < N; v++)
{
for(int u = 0; u < N; u++)
{
max_ben[v][u] = 0;
for(int k = 0; k < K; k++)
{
if(b[v][k] != -1 && s[u][k] != -1)
max_ben[v][u] = max(max_ben[v][u], s[u][k] - b[v][k]);
}
}
}
return;
}
bool Valid(ll x)
{
edges.clear();
ll w[maxn][maxn], d[maxn];
for(int v = 0; v < N; v++)
{
d[v] = inf;
for(int u = 0; u < N; u++)
{
w[v][u] = x * dis[v][u] - max_ben[v][u];
edges.push_back({v, u});
}
}
d[0] = 0;
for(int i = 0; i < N; i++)
{
for(auto tmp : edges)
{
int v = tmp.v, u = tmp.u;
if(d[u] > d[v] + w[v][u])
{
d[u] = d[v] + w[v][u];
}
}
}
for(auto tmp : edges)
{
int v = tmp.v, u = tmp.u;
if(d[u] > d[v] + w[v][u])
{
d[u] = d[v] + w[v][u];
return true;
}
}
return false;
}
int Bs(int l, int r)
{
if(r - l <= 1)
{
return l;
}
int mid = (l + r) / 2;
if(Valid(mid))
return Bs(mid, r);
else
return Bs(l, mid);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> N >> M >> K;
for(int i = 0; i < N; i++)
for(int j = 0; j < K; j++)
cin >> b[i][j] >> s[i][j];
memset(dis, 63, sizeof dis);
for(int i = 0; i < M; i++)
{
int v, u, w;
cin >> v >> u >> w;
v--, u--;
dis[v][u] = w;
}
FloydWarshall();
CalcBen();
int ans = Bs(0, inf);
cout << ans << '\n';
return 0;
}
