#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 105, K = 1005;
__int128 dist[N][N], best[N][N], d[N][N];
ll s[N][K], b[N][K];
void solve()
{
ll n, m, k;
cin >> n >> m >> k;
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= k; j++)
cin >> b[i][j] >> s[i][j];
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= n; j++)
dist[i][j] = i == j ? 0 : 1e18;
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= n; j++)
for (ll x = 1; x <= k; x++)
if (b[i][x] != -1 and s[j][x] != -1)
best[i][j] = max(best[i][j], (__int128)s[j][x] - b[i][x]);
while (m--)
{
ll a, b, c;
cin >> a >> b >> c;
dist[a][b] = c;
}
for (ll k = 1; k <= n; k++)
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
// for (ll i = 1; i <= n; i++)
// for (ll j = 1; j <= n; j++) cout << (ll)dist[i][j] << " \n"[j == n];
ll l = 0, r = 1e13;
while (l <= r)
{
ll mid = (l + r) >> 1;
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= n; j++)
d[i][j] = best[i][j] - dist[i][j] * mid;
for (ll k = 1; k <= n; k++)
for (ll i = 1; i <= n; i++)
for (ll j = 1; j <= n; j++)
d[i][j] = max(d[i][j], d[i][k] + d[k][j]);
bool ok = false;
for (ll i = 1; i <= n; i++) if (d[i][i] <= 0) ok = true;
if (ok) r = mid - 1;
else l = mid + 1;
}
cout << ++r << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
// precomp();
// cin >> t;
for (ll cs = 1; cs <= t; cs++)
solve();
// cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
