#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

struct node {
    int v , f;
    node *next , *rev;
} pool[142000] , *g[12000];
int top;
int n , m , k;
int s , t;
int x[12] , y[12] , u[12];
int level[12000];
void clear () {
    int i;
    for ( i = 1 ; i <= top ; i++ ) {
        pool[i] = pool[0];
    }
    for ( i = 1 ; i <= t ; i++ ) {
        g[i] = NULL;
    }
    top = 0;
}
void add ( int u , int v , int f ) {
    node *tmp1 = &pool[++top] , *tmp2 = &pool[++top];
    tmp1 -> v = v; tmp1 -> f = f; tmp1 -> next = g[u]; g[u] = tmp1; tmp1 -> rev = tmp2;
    tmp2 -> v = u; tmp2 -> f = 0; tmp2 -> next = g[v]; g[v] = tmp2; tmp2 -> rev = tmp1;
}
bool makelevel () {
    int i , k;
    queue < int > q;
    for ( i = 1 ; i <= t ; i++ ) level[i] = -1;
    level[s] = 1; q.push ( s );
    while ( q.size () != 0 ) {
        k = q.front (); q.pop ();
        for ( node *j = g[k] ; j ; j = j -> next )
            if ( j -> f && level[j->v] == -1 ) {
                level[j->v] = level[k] + 1;
                q.push ( j -> v );
                if ( j -> v == t ) return true;
            }
    }
    return false;
}
int find ( int k , int key ) {
    if ( k == t ) return key;
    int i , s = 0;
    for ( node *j = g[k] ; j ; j = j -> next )
        if ( j -> f && level[j->v] == level[k] + 1 && s < key ) {
            i = find ( j -> v , min ( key - s , j -> f ) );
            j -> f -= i;
            j -> rev -> f += i;
            s += i;
        }
    if ( s == 0 ) level[k] = -1;
    return s;
}
int dinic () {
    int ans = 0;
    while ( makelevel () == true ) ans += find ( s , 9999999 );
    //printf ( "%d\n" , ans );
    return ans;
}
int check ( int dis ) {
    int i , j , l , now , cnt[120];
    clear ();
    for ( i = 1 ; i <= k ; i++ ) {
        add ( 1 , 1 + i , u[i] );
    }
    for ( i = 0 ; i < (1<<k) ; i++ ) {
        cnt[i] = 0;
    }
    for ( j = 1 ; j <= n ; j++ ) {
        for ( l = 1 ; l <= m ; l++ ) {
            now = 0;
            for ( i = 1 ; i <= k ; i++ ) {
                if ( abs(x[i]-j)+abs(y[i]-l) <= dis ) {
                    now |= (1<<(i-1));
                }
            }
            cnt[now]++;
        }
    }
    for ( i = 0 ; i < (1<<k) ; i++ ) {
        add ( 1 + k + i + 1 , t , cnt[i] );
        for ( j = 1 ; j <= k ; j++ ) {
            if ( i & (1<<(j-1)) ) {
                add ( 1 + j , 1 + k + i + 1 , 9999999 );
            }
        }
    }
    if ( dinic () == n * m ) return 1;
    return 0;
}
void work () {
    int i , j , l , r , mid , ans;
    scanf ( "%d%d%d" , &n , &m , &k );
    for ( i = 1 ; i <= k ; i++ ) {
        scanf ( "%d%d%d" , &x[i] , &y[i] , &u[i] );
    }
    s = 1; t = 1 + k + (1<<k) + 1;
    l = 0; r = 2102;
    while ( l < r - 1 ) {
        mid = (l+r)/2;
        if ( check ( mid ) == 1 ) r = mid;
        else l = mid;
    }
    if ( check ( l ) ) ans = l;
    else ans = r;
    if ( ans >= 2050 ) ans = -1;
    printf ( "%d\n" , ans );
}
int main () {
    int t;
    scanf ( "%d" , &t );
    while ( t-- ) work ();
    return 0;
}