#include <bits/stdc++.h>

using namespace std;

namespace jumpmelon
{
    const int MAXK = 6;
    int n, m, k, F[(1 << MAXK) + 3];
    struct window
    {
        int x, y, z;
    } W[MAXK];

    inline int dis(int x, int y, int i) { return abs(x - W[i].x) + abs(y - W[i].y); }

    bool judge(int mid)
    {
        memset(F, 0, sizeof(int[1 << k]));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                int S = 0;
                for (int p = 0; p < k; p++)
                    if (dis(i, j, p) <= mid)
                        S |= 1 << p;
                F[S]++;
            }
        for (int S = 0; S < (1 << k); S++)
        {
            int v1 = 0, v2 = F[0];
            for (int i = 0; i < k; i++)
                if (S >> i & 1)
                    v1 += W[i].z;
            for (int T = S; T; T = (T - 1) & S)
                v2 += F[T];
            if (v1 < v2)
                return 0;
        }
        return 1;
    }

    void work()
    {
        int kase;
        scanf("%d", &kase);
        while (kase--)
        {
            int s = 0;
            scanf("%d%d%d", &n, &m, &k);
            for (int i = 0; i < k; i++)
            {
                scanf("%d%d%d", &W[i].x, &W[i].y, &W[i].z);
                s += W[i].z;
            }
            if (s < n * m)
            {
                puts("-1");
                continue;
            }
            int a = 0, b = n + m - 2;
            while (a < b)
            {
                int mid = (a + b) >> 1;
                if (judge(mid))
                    b = mid;
                else
                    a = mid + 1;
            }
            printf("%d\n", a);
        }
    }
}

int main()
{
    jumpmelon::work();
    return 0;
}