#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) {}
#define eprintf(...) do {} while(0)
#endif

template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename T>
ostream& operator << (ostream& out, const vector<T> &v) {
    int n = v.size();
    out << "{";
    for(int i = 0; i < n; ++i) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "}";
}
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &v) {
    return out << "(" << v.first << ", " << v.second << ")";
}

template<int maxN, int maxM>
struct Dinic {
    int n, m, s, t;
    struct Edge {
        int from, to, last;
        int flow, cap;
        Edge() {}
        Edge(int f, int t, int l, int fl, int cp) :
            from(f), to(t), last(l), flow(fl), cap(cp) {}
    } edges[maxM << 1]; int h[maxN];
    void init(int n) {
        this->n = n;
        m = 1;
        for(int u = 0; u <= n; ++u) h[u] = 0;
    }
    void link(int x, int y, int z) {
        edges[++m] = Edge(x, y, h[x], 0, z); h[x] = m;
        edges[++m] = Edge(y, x, h[y], 0, 0); h[y] = m;
    }
    int cur[maxN], d[maxN];
    bool BFS() {
        for(int u = 0; u <= n; ++u) d[u] = 0x3f3f3f3f;
        queue<int> Q; Q.push(s); d[s] = 1;
        while(Q.size()) {
            int u = Q.front(); Q.pop();
            for(int i = h[u]; i; i = edges[i].last) {
                const Edge &e = edges[i];
                if(e.cap > e.flow && d[e.to] == 0x3f3f3f3f) {
                    d[e.to] = d[u] + 1;
                    Q.push(e.to);
                }
            }
        }
        return d[t] != 0x3f3f3f3f;
    }
    int DFS(int u, int a) {
        if(u == t || a == 0) return a;
        int flow = 0, f;
        for(int &i = cur[u]; i; i = edges[i].last) {
            const Edge &e = edges[i];
            if(d[e.to] == d[u] + 1 && (f = DFS(e.to, std::min(a, e.cap - e.flow))) > 0) {
                flow += f; a -= f;
                edges[i].flow += f;
                edges[i ^ 1].flow -= f;
            }
            if(a == 0) break;
        }
        return flow;
    }
    int maxflow(int s, int t) {
        this->s = s; this->t = t;
        int flow = 0;
        while(BFS()) {
            for(int u = 0; u <= n; ++u) cur[u] = h[u];
            flow += DFS(s, 0x3f3f3f3f);
        }
        return flow;
    }
};

typedef long long LL;
typedef pair<int, int> pii;

const int maxN = 1000 + 5;
const int maxK = 6;
int n, m, k;
vector< pair<pii, int> > vp;
int dist(pii a, pii b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

Dinic<(1 << maxK) + maxK + 10, (1 << maxK) * (maxK + 3)> sol;

int f[1 << maxK];
bool check(int th) {
    memset(f, 0, sizeof(f));
    sol.init((1 << k) + k + 2);
    for(int x = 1; x <= n; ++x)
        for(int y = 1; y <= m; ++y) {
            int S = 0;
            for(int i = 0; i < k; ++i)
                if(dist(pii(x, y), vp[i].first) <= th)
                    S |= (1 << i);
            if(S == 0) return false;
            f[S]++;
        }
    int source = (1 << k) + k, sink = (1 << k) + k + 1;
    for(int i = 0; i < k; ++i) {
        int u = (1 << k) + i;
        sol.link(source, u, vp[i].second);
        for(int S = 1; S < (1 << k); ++S) if(S >> i & 1)
            sol.link(u, S, n * m);
    }
    for(int S = 1; S < (1 << k); ++S) sol.link(S, sink, f[S]);
    return sol.maxflow(source, sink) == n * m;
}

int solve() {
    cin >> n >> m >> k;
    vp.clear();
    for(int i = 0; i < k; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        vp.emplace_back(pii(x, y), z);
    }
    
    int L = 0, R = n + m;
    if(!check(R)) return -1;
    while(L < R) {
        int M = (L + R) >> 1;
        if(check(M)) R = M;
        else L = M + 1;
    }
    return L;
}

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
#endif
    int T; cin >> T;
    while(T--) cout << (solve()) << endl;
    return 0;
}