#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
    x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }

const int N = 1005,M = 1005,K = 6+1;
int n,m,k;
int px[K],py[K],pz[K];
int cnt[1<<6],p[1<<6],p2[7];

const int V = 10050,E = 40050;
int To[E],Ne[E],He[V],Flow[V],Now[V],_;
int cntv;
inline void add(int x,int y,int flow){
    ++_; To[_] = y,Ne[_] = He[x],He[x] = _;Flow[_] = flow;
    ++_; To[_] = x,Ne[_] = He[y],He[y] = _;Flow[_] = 0;
}
int S,T;
int dis[V],Q[V],ql,qr;
inline bool Bfs(){
    int i,x,y,p;
    for (i = 1; i <= cntv; ++i) dis[i] = 100000000;
    Q[ql=qr=1]=S,dis[S] = 0;
    while (ql<=qr){
        x = Q[ql],++ql;
        for (p = He[x]; p ; p = Ne[p]) if (Flow[p] && dis[y=To[p]] > dis[x]+1){
            dis[y] = dis[x] + 1;
            Q[++qr] = y;
        }
    }
    return dis[T] < 100000000;
}
inline int Dfs(int x,int flow){
    if (x == T || !flow) return flow;
    int rest = flow,p,y,f;
    for (p = Now[x]; p ; p = Ne[p]){
        Now[x] = p;
        if (Flow[p] && dis[y=To[p]] == dis[x] + 1){
            f = Dfs(y,min(rest,Flow[p]));
            Flow[p] -= f,rest -= f,Flow[p^1] += f;
            if (!rest) return flow;
        }
    }
    dis[x] = -1;
    return flow-rest;
}
inline int Dinic(){
    int tot = 0;
    while (Bfs()){
        for (int i = 1; i <= cntv; ++i) Now[i] = He[i];
        tot += Dfs(S,n*m);    
    }
    
    return tot;
}
inline bool check(int Mid){
    int i,j,t,s;
    for (i = 0; i <= cntv; ++i) He[i] = 0; _ = 1; cntv = 0;
    
    S = 1,T=cntv=2;
    for (i = 0; i < (1<<k); ++i) p[i] = ++cntv;
    for (i = 1; i <= k; ++i) p2[i] = ++cntv,add(S,p2[i],pz[i]);
    for (i = 1; i <= k; ++i)
    for (j = 0; j < (1<<k); ++j) if (j>>(i-1)&1) add(p2[i],p[j],n*m);
    memset(cnt,0,sizeof(cnt));
    for (i = 1; i <= n; ++i) for (j = 1; j <= m; ++j){
        for (s = 0,t = 1; t <= k; ++t) if (abs(px[t]-i) + abs(py[t]-j) <= Mid) s |= 1<<t-1;
        ++cnt[s];
    }
    for (i = 0; i < (1<<k); ++i) add(p[i],T,cnt[i]);
    return Dinic() == n*m;
}
inline void solve(){
    read(n),read(m),read(k);
    int i;
    for (i = 1; i <= k; ++i) read(px[i]),read(py[i]),read(pz[i]);
    int L = 0,R = n+m+2,Mid,Ans = -1;
    while (L <= R){
        Mid = L+R>>1;
        if (check(Mid)) Ans=Mid,R=Mid-1; else L=Mid+1;
    }
    cout << Ans<<'\n';
}
int main(){
    int T; read(T); while (T--) solve();
    return 0;
}