merchant

#include <iostream>
#include <cstdio>
#define task ""

using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e3 + 2;
int n, m, k;
ll buy[102][N], sell[102][N];
ll a[102][102];
ll best[102][102];
const ll Inf = 1e11;
ll d[N][N];

void Read()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= k; ++j)
            cin >> buy[i][j] >> sell[i][j];
    fill_n(&a[0][0], 102 * 102, Inf);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        a[u][v] = min(a[u][v], w);
    }
}

bool Check(ll x)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)
                d[i][j] = 0;
            else
                d[i][j] = a[i][j] == Inf ? Inf : (a[i][j] * x - best[i][j]),
                d[i][j] = min(d[i][j], Inf);
    for (int k = 1; k <= n; ++k)
        for (int u = 1; u <= n; ++u)
            for (int v = 1; v <= n; ++v)
                d[u][v] = min(d[u][v], d[u][k] == Inf || d[k][v] == Inf ? Inf : (d[u][k] + d[k][v])),
                d[u][v] = min(d[u][v], Inf);
    //cout << x << ":\n";
    //for (int u = 1; u <= n; ++u)
    //    for (int v = 1; v <= n; ++v)
    //        cout << d[u][v] << (v == n ? "\n" : " ");
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i != j && (d[j][i] == Inf || a[i][j] == Inf ? Inf : (d[j][i] + a[i][j] * x - best[i][j])) <= 0ll)
            {
                //cout << i << " " << j << " " << a[i][j] * x << " " << (d[j][i] == Inf || a[i][j] == Inf ? Inf : (d[j][i] + a[i][j] * x - best[i][j])) << "\n";
                return true;
            }
    return false;
}

void Solve()
{
    for (int u = 1; u <= n; ++u)
        a[u][u] = 0;
    for (int k = 1; k <= n; ++k)
        for (int u = 1; u <= n; ++u)
            for (int v = 1; v <= n; ++v)
                a[u][v] = min(a[u][v], a[u][k] + a[k][v]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            best[i][j] = 0;
            if (i != j)
                for (int t = 1; t <= k; ++t)
                    if (buy[i][t] != -1 && sell[j][t] != -1)
                        best[i][j] = max(best[i][j], sell[j][t] - buy[i][t]);
        }
    //for (int i = 1; i <= n; ++i)
    //    for (int j = 1; j <= n; ++j)
    //        cout << best[i][j] << (j == n ? "\n" : " ");
    ll l = 0, m, h = 1e9;
    while (l <= h)
    {
        m = (l + h) / 2;
        if (Check(m))
            l = m + 1;
        else
            h = m - 1;
    }
    cout << h;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}