#ifdef D
#include "hpp.hpp"
#else
#include <bits/stdc++.h>
#endif

using namespace std;

using I = long long;

class Main {
    struct C {
        I c;
        I x;
        I y;

        bool operator<(C const &t) const { return c < t.c; }
    };

    vector<C> cs;
    vector<I> ds;
    I const M, M1, N, N1;

    I find(I i) { return i == ds[i] ? i : ds[i] = find(ds[i]); }
    inline bool merge(I i, I j) {
        I const fi = find(i), fj = find(j);
        if (fi == fj) {
            return false;
        }
        ds[fj] = fi;
        return true;
    }

public:
    Main(I m, I n) : M(m), M1(m + 1), N(n), N1(n + 1) {
        cs.resize(M * N << 1);
        ds.resize(M1 * N1, 0);
        I i, j, t = 0, u, v, w = M1;
        for (i = 1; i <= N; ++i) {
            ++w;
            for (j = 1; j <= M; ++j, ++w) {
                scanf("%lld%lld", &u, &v);
                cs[t++] = { u, w - 1, w };
                cs[t++] = { v, w - M1, w };
                ds[w] = w;
            }
        }
        for (i = 1; i <= N; ++i) {
            ds[i * M1 + M] = 0;
        }
        for (j = 1; j <= M; ++j) {
            ds[N * M1 + j] = 0;
        }
    }

    void main() {
        I s = 0, z = (M - 1) * (N - 1);
        sort(cs.begin(), cs.end());
        for (C const &c : cs) {
            if (!z) {
                printf("%lld\n", s);
                return;
            }
            if (merge(c.x, c.y)) {
                s += c.c;
                --z;
            }
        }
    }
};

int main() {
    I m, n, t;
    for (scanf("%lld", &t); t; --t) {
        scanf("%lld%lld", &n, &m);
        Main main(m, n);
        main.main();
    }
}