#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100005;

struct Edge
{
    int x, y, cost;
    bool operator < (Edge b) const
    {
        return (this -> cost < b.cost);
    }
}a[2 * N];

int t[N], n, m, nmax;


inline void Union (int x, int y)
{
    t[x] = y;
}

int Find (int x)
{
    int root, y;
    root = x;
    while (t[root] != 0)
        root = t[root];
    while (x != root)
    {
        y = t[x];
        t[x] = root;
        x = y;
    }
    return root;
}

int APM ()
{
    long long totalcost = 0;
    int i;
    sort (a + 1, a + m + 1);
    for (i = 1; i <= m; i++)
    {
        int j, k;
        j = Find(a[i].x);
        k = Find(a[i].y);
        if (j != k)
        {
            Union(j, k);
            totalcost += a[i].cost;
        }
    }
    for (i = 1; i < n; i++)
        if (Find(i) != Find(i + 1)) return -1;
    return totalcost;
}

void Read ()
{
    ifstream fin ("alegeri.in");
    ofstream fout ("alegeri.out");
    int tests, type, i;
    fin >> tests;
    while (tests--)
    {
        fin >> n >> m;
        nmax = max(nmax, n);
        for (i = 1; i <= nmax; i++)
            t[i] = 0;
        for (i = 1; i <= m; i++)
        {
            fin >> type;
            fin >> a[i].x >> a[i].y;
            if (!type)
                a[i].cost = 0;
            else fin >> a[i].cost;
        }
        fout << APM () << "\n";
    }
}

int main()
{
    Read();
    return 0;
}