#include <bits/stdc++.h>
using namespace std;
using lli = long long;
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> bs(n, vector<int>(k)), ss(n, vector<int>(k));
for (int i = 0; i < n; ++i)
for (int j = 0; j < k; ++j)
cin >> bs[i][j] >> ss[i][j];
vector<vector<lli>> dist(n, vector<lli>(n, 1e18));
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
dist[u - 1][v - 1] = w;
}
for (int i = 0; i < n; ++i)
dist[i][i] = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int z = 0; z < n; ++z)
if (dist[j][z] > dist[j][i] + dist[i][z])
dist[j][z] = dist[j][i] + dist[i][z];
vector<vector<int>> profit(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
for (int z = 0; z < k; ++z) if (ss[j][z] != -1 && bs[i][z] != -1)
profit[i][j] = max(profit[i][j], ss[j][z] - bs[i][z]);
// cerr << "PROFIT " << i << " " << j << " "<< profit[i][j] << "\n";
}
auto bellman = [&](lli x) {
vector<lli> pot(n);
// cerr << "-> " << x << "\n";
for (int i = 0; i <= n + 1; ++i) {
bool change = false;
for (int u = 0; u < n; ++u)
for (int v = 0; v < n; ++v) if (u != v && dist[u][v] != 1e18) {
lli c = (dist[u][v]*x - profit[u][v])*100 - 1;
if (pot[v] > pot[u] + c) {
pot[v] = pot[u] + c;
// cerr << u << " " << v << " " << c << " CHANGE!\n";
change = true;
}
}
if (i == n + 1 && change) {
for (lli x: pot)
cerr << x << " ";
cerr << "\n";
return false;
}
if (!change) break;
}
// for (lli x: pot)
// cerr << x << " ";
// cerr << "\n";
return true;
};
lli l = 0, r = 1e7;
while (l < r) {
int m = (l + r)/2;
if (bellman(m)) r = m;
else l = m + 1;
}
cout << l-1 << "\n";
}
