#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 110, maxk = 1010;
const ll inf = 1e17;
int n, m, k;
ll dist[maxn][maxn], b[maxn][maxk], s[maxn][maxk];
ll profit[maxn][maxn], dp[maxn][maxn];
void floyd_warshall()
{
for (int p = 1; p <= n; p ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (dist[i][p] + dist[p][j] < dist[i][j])
{
dist[i][j] = dist[i][p] + dist[p][j];
}
}
}
void bin_floyd()
{
for (int p = 1; p <= n; p ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (dp[i][p] + dp[p][j] < dp[i][j])
{
dp[i][j] = dp[i][p] + dp[p][j];
}
}
}
void build_graph(ll mf)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j ++)
{
dp[i][j] = mf * min(dist[i][j], inf / mf) - profit[i][j];
///cout << i << " " << j << " " << dp[i][j] << " : " << dist[i][j] << " : " << profit[i][j] << endl;
}
}
bool check(ll mf)
{
build_graph(mf);
bin_floyd();
bool neg = false;
for (int i = 1; i <= n; i ++)
if (dp[i][i] <= 0)
neg = true;
return neg;
}
void solve()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
dist[i][j] = inf;
for (int j = 1; j <= k; j ++)
cin >> b[i][j] >> s[i][j];
}
for (int i = 1; i <= m; i ++)
{
int v, u;
ll w;
cin >> v >> u >> w;
dist[v][u] = min(dist[v][u], w);
}
floyd_warshall();
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
for (int p = 1; p <= k; p ++)
{
if (s[j][p] != -1 && b[i][p] != -1)
{
profit[i][j] = max(profit[i][j], s[j][p] - b[i][p]);
}
}
ll lf = 0, rf = 1e9;
while(lf <= rf)
{
ll mf = (lf + rf) / 2;
if (check(mf))
lf = mf + 1;
else
rf = mf - 1;
}
cout << max((ll)0, rf) << endl;
}
int main()
{
solve();
return 0;
}
