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

const int maxn=1005;
const int maxm=6;
int T,n,m,k,sum;
int x[maxm],y[maxm],z[maxm],cnt[1<<maxm];
pair<int,int>ord[maxn][maxn][maxm];

bool check(int d){
    for(int mask=0;mask<(1<<k);mask++)cnt[mask]=0;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        int pos=lower_bound(ord[i][j],ord[i][j]+k,make_pair(d+1,-1))-ord[i][j]-1;
        if(pos<0)return false;
        cnt[ord[i][j][pos].second]++; 
    }
    int val=sum;
    for(int mask=0;mask<(1<<k);mask++){
        int cur=0;
        for(int i=0;i<k;i++)if((mask>>i)&1)cur+=z[i];
        for(int sub=0;sub<(1<<k);sub++)
            if((mask&sub)!=sub)cur+=cnt[sub];
        val=min(val,cur);
    }
    return val==n*m;
} 

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        sum=0;
        for(int i=0;i<k;i++){
            scanf("%d%d%d",&x[i],&y[i],&z[i]);
            x[i]--;y[i]--;
            sum+=z[i];
        }
        if(sum<n*m){
            puts("-1");
            continue;
        }
        for(int i=0;i<n;i++)for(int j=0;j<m;j++){
            for(int p=0;p<k;p++)
                ord[i][j][p].first=abs(i-x[p])+abs(j-y[p]),ord[i][j][p].second=(1<<p);
            sort(ord[i][j],ord[i][j]+k);
            for(int p=1;p<k;p++)
                ord[i][j][p].second|=ord[i][j][p-1].second;
        }
        int l=-1,r=n+m;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid))r=mid;
            else l=mid+1;
        }
        printf("%d\n",r);
    }
    return 0;
}