#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
};
template <typename T> struct vvv : vector <vv <T>> {
vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
};
#ifdef Doludu
#define test(args...) info(), abc("[" + string(#args) + "]", args)
#define owo
#else
#define test(args...)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 998244353, N = 1000001, logN = 20, K = 111;
int main () {
owo;
int n, m, k;
cin >> n >> m >> k;
vv <pii> a(n, k, mp(0, 0));
for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) cin >> a[i][j];
vv <int> dis(n, n, 1e9 + 87);
vv <long long> profit(n, n, 0);
for (int i = 0; i < n; ++i) dis[i][i] = 0;
for (int i = 0, u, v, w; i < m; ++i) {
cin >> u >> v >> w, --u, --v;
dis[u][v] = min(dis[u][v], w);
}
for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
for (int t = 0; t < k; ++t) {
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
if (a[i][t].X == -1 || a[j][t].X == -1) continue;
profit[i][j] = max(profit[i][j], (long long)a[j][t].Y - a[i][t].X);
}
}
auto chk = [&](long long x) {
vv <long long> d(n, n, 1ll << 60);
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
if (i == j) d[i][j] = 1;
else {
d[i][j] = x * dis[i][j] - profit[i][j];
}
}
for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != k && j != k) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
if (i == j && d[i][i] <= 0) return true;
}
// a / b >= x
// a >= b * x
// b * x - a <= 0
return false;
};
long long l = 0, r = 1 << 30;
while (r - l > 1) {
long long mid = l + r >> 1;
if (chk(mid)) l = mid;
else r = mid;
}
cout << l << endl;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/
Compilation message
koala.cpp: In function 'int main()':
koala.cpp:87:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | long long mid = l + r >> 1;
| ~~^~~
/usr/bin/ld: /tmp/cccbJ8RU.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccOnsmcU.o:koala.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cccbJ8RU.o: in function `runGame(int)':
grader.cpp:(.text+0x157): undefined reference to `minValue(int, int)'
/usr/bin/ld: grader.cpp:(.text+0x191): undefined reference to `allValues(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text+0x1d7): undefined reference to `maxValue(int, int)'
/usr/bin/ld: grader.cpp:(.text+0x207): undefined reference to `greaterValue(int, int)'
collect2: error: ld returned 1 exit status
