#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100;
const int K = 1000;
const ll INF = 1'000'000'000'000'000'000;
const ll INF9 = 1'000'000'000;
int n, m, k;
ll b[N + 10][K + 10], s[N + 10][K + 10];
ll len[N + 10][N + 10], w[N + 10][N + 10];
ll dis[N + 10][N + 10], e[N + 10][N + 10];
ll x[N + 10][N + 10], y[N + 10][N + 10];
void readInput() {
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;
cin >> u >> v;
cin >> e[u][v];
}
}
void calcFloyd() {
for (int i = 1; i <= n; i++) {
dis[i][i] = 0;
for (int j = 1; j <= n; j++)
if (j != i)
dis[i][j] = w[i][j];
}
for (int x = 1; x <= n; x++)
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
dis[u][v] = min(dis[u][v], dis[u][x] + dis[x][v]);
}
void calcLen() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
w[i][j] = (e[i][j]? e[i][j]: INF);
calcFloyd();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
len[i][j] = dis[i][j];
}
void calcXY() {
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++) {
x[u][v] = -1;
y[u][v] = len[u][v];
for (int i = 1; i <= k; i++)
if (len[u][v] != INF && b[u][i] != -1 && s[v][i] != -1 && s[v][i] > b[u][i]) {
x[u][v] = max(x[u][v], s[v][i] - b[u][i]);
}
if (len[u][v] != INF)
x[u][v] = max(x[u][v], 0ll);
}
}
void calcW(ll res) {
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
if (x[u][v] != -1)
w[u][v] = y[u][v] * res - x[u][v];
else
w[u][v] = INF;
}
bool check(ll res) {
calcW(res);
calcFloyd();
for (int i = 1; i <= n; i++) {
if (dis[i][i] < 0)
return true;
for (int j = 1; j <= n; j++)
if (i != j && dis[i][j] + w[j][i] == 0)
return true;
}
return false;
}
void calcAns() {
ll l = 0, r = INF9 + 1;
while (r - l > 1) {
ll mid = (l + r) >> 1;
if (check(mid))
l = mid;
else
r = mid;
}
cout << l << flush;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
calcLen();
calcXY();
calcAns();
return 0;
}
