#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
#define int ll
const int INF = 1e9 + 1;
vector<int> dijkstra(int n, vector<vector<pair<int, int>>> g, int s) {
vector<int> dist(n, INF);
dist[s] = 0ll;
set<pair<int, int>> st;
for (int i = 0; i < n; i++) st.insert({dist[i], i});
while (!st.empty()) {
auto [d, v] = *st.begin();
st.erase({d, v});
for (auto &[u, w] : g[v]) {
if (dist[u] > d + w) {
st.erase({dist[u], u});
dist[u] = d + w;
st.insert({dist[u], u});
}
}
}
return dist;
}
void solve() {
int n, m, k; cin >> n >> m >> k;
vector<vector<int>> b(n, vector<int>(k)), s(n, vector<int>(k));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
cin >> b[i][j] >> s[i][j];
}
}
vector<vector<int>> maxprof(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
for (int kk = 0; kk < k; kk++) {
//cout << i << ' ' << j << '\n';
if (b[i][kk] != -1 && s[j][kk] != -1) {
maxprof[i][j] = max(maxprof[i][j], s[j][kk] - b[i][kk]);
}
}
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << maxprof[i][j] << ' ';
// }
// cout << '\n';
// }
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
u--; v--;
g[u].pb({v, w});
}
vector<vector<int>> dj(n, vector<int>(n));
for (int i = 0; i < n; i++) dj[i] = dijkstra(n, g, i);
int L = 0, R = 1e9 + 1;
while (R - L > 1) {
int M = (L + R) / 2;
vector<vector<int>> d(n, vector<int>(n, INF));
for (int i = 0; i < n; i++) d[i][i] = 0;
//cout << M << '\n';
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (dj[i][j] != INF) d[i][j] = dj[i][j] * M;
for (int vt = 0; vt < n; vt++) {
if (dj[i][vt] != INF && dj[vt][j] != INF) {
d[i][j] = min(d[i][j], (dj[i][vt] + dj[vt][j]) * M - maxprof[vt][j]);
}
}
}
}
for (int K=0; K<n; ++K)
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
d[i][j] = min (d[i][j], d[i][K] + d[K][j]);
bool loop = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (d[i][j] + d[j][i] <= 0) loop = true;
}
}
if (loop) L = M;
else R = M;
}
cout << L << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}
