#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int maxn=1e5+3;
struct edge{
    int to,c;
};
edge e[maxn];
int h[maxn],nxt[maxn],X[6],Y[6],Z[6];
int a[maxn],n,m,p,s,t,cnt[64];
int dis[maxn],sz[maxn];
void add_edge(int x,int y,int z){
    e[p].to=y;e[p].c=z;nxt[p]=h[x];h[x]=p;sz[x]++;p++;
    e[p].to=x;e[p].c=0;nxt[p]=h[y];h[y]=p;sz[y]++;p++;
}
bool bfs(){
    queue <int> q;
    for (int i=1;i<=n;i++) dis[i]=-1;
    dis[s]=0;
    q.push(s);
    while (!q.empty()){
        int cur=q.front();q.pop();
        for (int i=h[cur];i!=-1;i=nxt[i]){
            int tt=e[i].to;
            if (dis[tt]==-1&&e[i].c>0){
                dis[tt]=dis[cur]+1;
                q.push(tt);
            }
        }
    }
    return (dis[t]!=-1);
}
int findf(int x,int flow){
    if (x==t) return flow;
    int a;
    for (int i=h[x];i!=-1;i=nxt[i]){
        int tt=e[i].to;
        if (dis[tt]==dis[x]+1&&e[i].c>0&&(a=findf(tt,min(flow,e[i].c)))){
            e[i].c-=a;
            e[i^1].c+=a;
            return a;
        }
    }
    return 0;
}
int dinic(){
    int tmp,ans;ans=0;
    while (bfs()){
        tmp=findf(s,inf);
        ans+=tmp;
    }
    return ans;
}
void init(int n){
    for (int i=1;i<=n;i++) h[i]=-1;
    p=0;
}
void solve(){
    int N,M,K,l,r,mid;
    scanf("%d%d%d",&N,&M,&K);
    l=-1; r=N+M-2;
    for (int i=0;i<K;i++) scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
    int sum=0;
    for (int i=0;i<K;i++) sum+=Z[i];
    if (sum<N*M){puts("-1");return;}
    while (r-l>1){
        mid=(l+r)/2;
        memset(cnt,0,sizeof(cnt));
        for (int i=1;i<=N;i++)
        for (int j=1;j<=M;j++){
            int mask=0;
            for (int k=0;k<K;k++) if (abs(i-X[k])+abs(j-Y[k])<=mid) mask|=1<<k;
            cnt[mask]++;
        }
        n=K+(1<<K)+2;
        init(n);
        s=1; t=n;
        for (int i=0;i<K;i++) add_edge(s,i+2,Z[i]);
        for (int i=0;i<(1<<K);i++)
            for (int j=0;j<K;j++) if (i&(1<<j)) add_edge(j+2,i+K+2,1e8);
        for (int i=0;i<(1<<K);i++) add_edge(i+K+2,t,cnt[i]);
        if (dinic()==N*M) r=mid; else l=mid;
    }
    printf("%d\n",r);
}
int main(){
    int _; scanf("%d",&_);
    while (_--) solve();
    return 0;
}