//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e2, K = 1e3;
const long long oo = 1e18 + 1;
long long d[N + 1][K + 1];
int n, m, k, b[N + 1][K + 1], s[N + 1][K + 1];
vector<pair<int, int> > adj[N + 1];
void read()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; ++ i)
{
for (int j = 1; j <= k; ++ j)
{
cin >> b[i][j] >> s[i][j];
}
}
for (int i = 1; i <= m; ++ i)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
//adj[v].push_back({u, w});
}
}
bool check(long long x)
{
priority_queue<tuple<long long, int, int> > PQ;
fill(&d[0][0], &d[0][0] + sizeof(d)/sizeof(d[0][0]), -oo);
PQ.push(make_tuple(0, 1, 0));
while(!PQ.empty())
{
long long r;
int u, item;
tie(r, u, item) = PQ.top();
PQ.pop();
if (d[1][0] >= 0)
{
return true;
}
if (d[u][item] > r)
{
continue;
}
//cerr << u << ' ' << r << ' ' << item << '\n';
if (item != 0 && s[u][item] != -1)
{
long long money = min(oo, r + s[u][item]);
if (d[u][0] < money)
{
d[u][0] = money;
PQ.push(make_tuple(money, u, 0));
}
}
if (item == 0)
{
for (int j = 1; j <= k; ++ j)
{
if (b[u][j] != -1)
{
long long money = r - b[u][j];
if (d[u][j] < money)
{
d[u][j] = money;
PQ.push(make_tuple(money, u, j));
}
}
}
}
for (auto p : adj[u])
{
int v = p.first, w = p.second;
if (d[v][item] < r - x * w)
{
d[v][item] = r - x * w;
PQ.push(make_tuple(d[v][item], v, item));
}
}
}
return false;
}
void solve()
{
long long low = 1, high = 1e10;
while(low <= high)
{
int mid = (low + high)/2;
if (check(mid))
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
cout << high;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
