#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <cassert>

#include <iostream>

#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <algorithm>
#include <utility>
#include <memory>
#include <bitset>
#include <string>
#include <tuple>
using namespace std;

#define lowbit(x) ((x) & -(x))
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define ls id<<1
#define rs id<<1|1
#define MID(l,r) ((l)+(((r)-(l))>>1))
#define fi first
#define se second
#define mk make_pair
#define mt make_tuple
#define pb push_back
#define epb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

using LL = long long;
//using LL = __int64;
using pii = pair<int, int>;
using pdd = pair<double, double>;
using pLL = pair<LL, LL>;

const int INF = 0x3f3f3f3f;
const LL LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int e5 = 100000; // 1e5
const int e6 = 1000000; //1e6;
const int MOD_1e9 = 1000000007; //1e9 + 7
const int MOD_998 = 998244353;
const int MOD = MOD_1e9;

template< typename T = int > inline T read()
{
    char c = '\0';
    bool f = false;
    T x = 0;
    while(c < '0' || '9' < c) {if(c == '-') f = true; c = getchar();}
    while('0' <= c && c <= '9') {x = (x << 1) + (x << 3) + (c & 0xf); c = getchar();}
    if(f) return -x;
    return x;
}
template< typename T > inline void read(T &x) {x = read<T>();}
template< typename T, typename ...Args > inline void read(T &x, Args &...args) {read(x); read(args...);}

template< typename T > inline void get_min(T &x, T y) {if(y < x) x = y;}
template< typename T > inline void get_max(T &x, T y) {if(x < y) x = y;}
template< typename T > inline void get_unique(vector<T> &vec) {sort(all(vec)); vec.erase(unique(all(vec)), vec.end());}

inline int sig(double x) {return x < -eps ? -1 : eps < x;}
LL fp(LL a, LL n, LL mod = MOD)
{
    if(n < 0) a = fp(a, mod - 2, mod), n = -n;
    LL res = 1;
    for(; n; n >>= 1, a = a * a % mod)
        if(n & 1)
            res = res * a % mod;
    return res;
}

template< int mod > struct Mint
{
    int x;
    Mint():x(0) {}
    Mint(int _x): x(_x) {if(x < 0 || x >= mod) x %= mod; if(x < 0) x += mod;}
    Mint(LL _x) {if(_x < 0 || _x >= mod) _x %= mod; if(_x < 0) _x += mod; x = _x;}
    Mint operator - () const {return Mint(mod - x);}
    Mint operator + (const Mint &rhs) const {return Mint(x + rhs.x >= mod ? x + rhs.x - mod : x + rhs.x);}
    Mint operator - (const Mint &rhs) const {return Mint(x - rhs.x < 0 ? x - rhs.x + mod : x - rhs.x);}
    Mint operator * (const Mint &rhs) const {return Mint((LL)x * rhs.x % mod);}
    Mint operator / (const Mint &rhs) const {return Mint((LL)x * fp(rhs.x, -1, mod) % mod);}
    bool operator == (const Mint &rhs) const {return x == rhs.x;}
    bool operator != (const Mint &rhs) const {return x != rhs.x;}
    Mint &operator += (const Mint &rhs) {x += rhs.x; if(x >= mod) x -= mod; return *this;}
    Mint &operator -= (const Mint &rhs) {x -= rhs.x; if(x < 0) x += mod; return *this;}
    Mint &operator *= (const Mint &rhs) {x = (LL)x * rhs.x % mod; return *this;}
    Mint &operator /= (const Mint &rhs) {x = (LL)x * fp(rhs.x, -1, mod) % mod; return *this;}
    friend ostream &operator << (ostream &out, const Mint &rhs) {return out << to_string(rhs.x);}
    Mint inv() {return Mint(fp(x, -1, mod));}
    Mint pow(int k) {return Mint(fp(x, k, mod));}
    Mint pow(const Mint &t) {return Mint(fp(x, t.x, mod));}
};

const int maxn = (int) 1e4 + 20;
const int maxm = (int) 2e6 + 20;


struct ISAP
{
    struct Edge
    {
        int from,to,cap,flow;
        Edge() {}
        Edge(int _from,int _to,int _cap,int _flow):from(_from),to(_to),cap(_cap),flow(_flow) {}
    };
    int n,m,s,t;
    vector<Edge> edge;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int p[maxn],num[maxn];

    void init(int _n,int _s,int _t)
    {
        n=_n; s=_s; t=_t; m=0;
        edge.clear();
        for(int i=0;i<=n;i++) G[i].clear();

        edge.reserve(maxn * 4);
    }

    void add_edge(int from,int to,int cap)
    {
        edge.emplace_back(Edge(from,to,cap,0));
        edge.emplace_back(Edge(to,from,0,0));
        m+=2;
        G[from].emplace_back(m-2);
        G[to].emplace_back(m-1);
    }

    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int> Q;
        Q.push(t);
        vis[t]=1;
        d[t]=0;
        while(!Q.empty())
        {
            int x=Q.front(); Q.pop();
            for(int i=0;i<G[x].size();i++)
            {
                Edge &e=edge[G[x][i]^1];
                if(!vis[e.from] && e.cap>e.flow)
                {
                    vis[e.from]=1;
                    d[e.from]=d[x]+1;
                    Q.emplace(e.from);
                }
            }
        }
        return vis[s];
    }

    int augment()
    {
        int x=t, a=0x3f3f3f3f;
        while(x!=s)
        {
            Edge &e=edge[p[x]];
            a=min(a,e.cap-e.flow);
            x=e.from;
        }
        x=t;
        while(x!=s)
        {
            edge[p[x]].flow+=a;
            edge[p[x]^1].flow-=a;
            x=edge[p[x]].from;
        }
        return a;
    }

    int Maxflow()
    {
        int flow=0;
        BFS();
        memset(num,0,sizeof(num));
        for(int i=0;i<=n;i++) num[d[i]]++;
        int x=s;
        memset(cur,0,sizeof(cur));
        while(d[s]<n)
        {
            if(x==t)
            {
                flow+=augment();
                x=s;
            }
            bool ok=0;
            for(int i=cur[x];i<G[x].size();i++)
            {
                Edge &e=edge[G[x][i]];
                if(e.cap>e.flow && d[x]==d[e.to]+1)
                {
                    ok=1;
                    p[e.to]=G[x][i];
                    cur[x]=i;
                    x=e.to;
                    break;
                }
            }
            if(!ok)
            {
                int m=n-1;
                for(int i=0;i<G[x].size();i++)
                {
                    Edge &e=edge[G[x][i]];
                    if(e.cap>e.flow) m=min(m,d[e.to]);
                }
                if(--num[d[x]]==0) break;
                num[d[x]=m+1]++;
                cur[x]=0;
                if(x!=s) x=edge[p[x]].from;
            }
        }
        return flow;
    }
}MF;


int n, m, k;
int x[6], y[6], w[6];
int dis[6][1111][1111];
int encode[1111][1111];
int cnt[1 << 6];

void work()
{
    read(n, m, k);

    for(int i = 0; i < k; i++)
        read(x[i], y[i], w[i]);

    int tot = 0;
    for(int i = 0; i < k; i++)
        tot += w[i];

    if(tot < n * m)
    {
        cout <<-1 <<endl;
        return ;
    }

    vector<int> dx{0, 1, 0, -1};
    vector<int> dy{-1, 0, 1, 0};

    auto f = [&](int x, int y, int k)
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                dis[k][i][j] = -1;

        dis[k][x][y] = 0;
        queue<pii> Q;
        Q.emplace(mk(x, y));
        while(!Q.empty())
        {
            int x = Q.front().fi, y = Q.front().se;
            Q.pop();

            for(int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(1 <= nx && nx <= n && 1 <= ny && ny <= m && dis[k][nx][ny] == -1)
                {
                    dis[k][nx][ny] = dis[k][x][y] + 1;
                    Q.emplace(mk(nx, ny));
                }
            }
        }
    };

    for(int i = 0; i < k; i++)
        f(x[i], y[i], i);


    int sour = (1 << k) + 6, dest = (1 << k) + 7;

    int l = 0, r = n + m, mid, ans = -1;
    while(l <= r)
    {
        mid = MID(l, r);
        MF.init(dest, sour, dest);

        for(int i = 0; i < (1 << k); i++)
            cnt[i] = 0;

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                encode[i][j] = 0;

        for(int kk = 0; kk < k; kk++)
        {
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                {
                    if(dis[kk][i][j] <= mid)
                        encode[i][j] |= 1 << kk;
                }
        }

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                cnt[encode[i][j]]++;

        if(cnt[0] != 0)
        {
            l = mid + 1;
            continue;
        }

        MF.init(dest, sour, dest);
        for(int i = 0; i < k; i++)
        {
            MF.add_edge(sour, (1 << k) + i, w[i]);
        }

        for(int i = 1; i < (1 << k); i++)
        {
            for(int j = 0; j < k; j++)
            {
                if((i >> j) & 1)
                {
                    MF.add_edge((1 << k) + j, i, INF);
                }
            }

            MF.add_edge(i, dest, cnt[i]);
        }

        int flow = MF.Maxflow();
        if(flow == n * m)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }

    cout <<ans <<endl;

}

int main()
{
#ifdef yukihana0416
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // yukihana0416

    int tc = 1;
    read(tc);
    for(int ca = 1; ca <= tc; ca++)
    {
//        printf("Case #%d: ", ca);
        work();
    }
    return 0;
}