#include<bits/stdc++.h>
  
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define sz(a) ((int)a.size())
#define pb push_back
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 1e3 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

template<class ll>
struct Dinic {
    struct Edge { int v, rev; ll cap; };
    vector<Edge> G[maxn];
    int dis[maxn], cur[maxn], n, sp, tp;
    void init(int nn) {
        n = nn;
        for (int i = 1; i <= n; ++i) G[i].clear();
    }
    void add(int u, int v, ll cap, ll rcap = 0) {
        G[u].pb({ v, sz(G[v]), cap });
        G[v].pb({ u, sz(G[u]) - 1, rcap });
    }
    int bfs() {
        queue<int> q;
        for (int i = 1; i <= n; ++i) dis[i] = 0;
        dis[sp] = 1, q.push(sp);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (Edge &e : G[u]) {
                if (e.cap && !dis[e.v]) {
                    dis[e.v] = dis[u] + 1;
                    if (e.v == tp) return 1;
                    q.push(e.v);
                }
            }
        }
        return 0;
    }
    ll dfs(int u, ll flow) {
        if (u == tp || !flow) return flow;
        ll ret = 0, tmp;
        for (int &i = cur[u]; i < sz(G[u]); ++i) {
            Edge &e = G[u][i];
            if (dis[e.v] == dis[u] + 1 && (tmp = dfs(e.v, min(e.cap, flow - ret)))) {
                e.cap -= tmp, G[e.v][e.rev].cap += tmp, ret += tmp;
                if (ret == flow) return ret;
            }
        }
        if (!ret) dis[u] = 0;
        return ret;
    }
    ll solve(int s, int t) {
        sp = s, tp = t;
        ll ret = 0;
        while (bfs()) {
            for (int i = 1; i <= n; ++i) cur[i] = 0;
            ret += dfs(sp, inf);
        }
        return ret;
    }
};

Dinic<int> dinic;
struct Node{
    int x, y, z;
} b[maxn];
int a[maxn][maxn], sta[maxn][maxn];
int n, m, k;

int judge(int mid){

    int S = (1 << k) + k + 1, T = S + 1;
    dinic.init(T);
    int cnt[233] = {};
    for(int i = 1; i <= n; ++i){

        for(int j = 1; j <= m; ++j){

            sta[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; ++i){

        for(int j = 1; j <= m; ++j){

            for(int o = 1; o <= k; ++o){

                int dt = abs(b[o].x - i) + abs(b[o].y - j);
                if(dt <= mid) sta[i][j] |= 1 << (o - 1);
            }
        }
    }
    for(int i = 1; i <= n; ++i){

        for(int j = 1; j <= m; ++j){

            ++cnt[sta[i][j]];
        }
    }
    if(cnt[0] > 0) return 0;
    for(int i = 1; i <= k; ++i){

        dinic.add(S, i, b[i].z);
    }
    for(int i = 0; i < (1 << k); ++i){

        for(int j = 0; j < k; ++j){

            if((i >> j) & 1){

                dinic.add(j + 1, k + 1 + i, inf);
            }
        }
        dinic.add(k + i + 1, T, cnt[i]);
    }
    return dinic.solve(S, T) >= n * m;
}

int main(){
 
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--){

        cin >> n >> m >> k;
        for(int i = 1; i <= k; ++i){

            cin >> b[i].x >> b[i].y >> b[i].z;
        }
        int l = 0, r = n + m, mid, ret = -1;
        while(l <= r){

            mid = gmid;
            if(judge(mid)) ret = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << ret << "\n";
    }
    return 0;
}