#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> b, s;
vector<vector<pair<int, int>>> adj;
ll dist[100][100], gain[100][100];
ll recip[100][100];
const ll BIG = 1234567891234567890;
int main() {
cout << fixed << setprecision(20);
int n, m, k;
cin >> n >> m >> k;
b.resize(n);
s.resize(n);
adj.resize(n);
for(int i = 0; i < n; i++) {
b[i].resize(k);
s[i].resize(k);
for(int j = 0; j < k; j++) {
cin >> b[i][j] >> s[i][j];
}
for(int j = 0; j < n; j++) {
dist[i][j] = BIG;
gain[i][j] = 0;
}
}
for(int i = 0; i < m; i++) {
int x, y, t;
cin >> x >> y >> t;
x--; y--;
adj[x].push_back({y, t});
dist[x][y] = t;
}
// floyd-warshall
for(int z = 0; z < n; z++) {
for(int x = 0; x < n; x++) {
for(int y = 0; y < n; y++) {
dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]);
}
}
}
// gain calculation
for(int x = 0; x < n; x++) {
for(int y = 0; y < n; y++) {
for(int i = 0; i < k; i++) {
if(b[x][i] == -1 || s[y][i] == -1) continue;
gain[x][y] = max(gain[x][y], s[y][i] - b[x][i]);
}
}
}
int l = 0, r = 1234567890;
while(l != r - 1) {
int mid = (l+r)/2;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j) recip[i][j] = BIG;
else recip[i][j] = dist[i][j] * mid - gain[i][j];
}
}
ll ans = 1;
for(int z = 0; z < n; z++) {
for(int x = 0; x < n; x++) {
for(int y = 0; y < n; y++) {
recip[x][y] = min(recip[x][y], recip[x][z] + recip[z][y]);
if(x == y) ans = min(ans, recip[x][y]);
}
}
}
if(ans <= 0) l = mid;
else r = mid;
}
cout << l << '\n';
}
