#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()

struct Edge {
    int u, v, w, c;  
} edges[85];

const int INF = 1e9;
int choose[85], tag[85], num[85], bound[85], boss[85];
vector<int> G[85];
pii dis[85];
int frm[85], inq[85];

int finds(int x) {
    if (x == boss[x]) return x;
    return boss[x] = finds(boss[x]);
}

bool Union(int x, int y) {
    x = finds(x), y = finds(y);
    if (x == y) return false;
    boss[x] = y;
    return true;
}

int cal(int n, int m) {
    int conn = n;
    iota(boss, boss + n, 0);
    for (int i = 0; i < m; ++i)
        if (!choose[i])
            conn -= Union(edges[i].u, edges[i].v);
    return conn;
}

int SPFA(int n) {
    fill_n(dis, n, make_pair(-INF, INF)), fill_n(inq, n, 0), fill_n(frm, n, -1);
    queue<int> q;
    auto relax = [&](int u, pii d, int f) {
        if (dis[u] < d) {
            dis[u] = d, frm[u] = f;
            if (!inq[u]) inq[u] = 1, q.push(u);
        }
    };
    auto wei = [&](int x) {
        if (choose[x]) return -edges[x].w;
        return edges[x].w;
    };
    for (int i = 0; i < n; ++i)
        if (tag[i] & 1)
            relax(i, pii(wei(i), 0), -1);
    while (!q.empty()) {
        int u = q.front();
        q.pop(), inq[u] = 0;
        for (int e : G[u]) {
            pii td = dis[u];
            td.X += wei(e);
            td.Y -= 1;
            relax(e, td, u);
        }
    }
    int mi = -1;
    for (int i = 0; i < n; ++i)
        if ((tag[i] & 2) && dis[i].X != -INF && (mi == -1 || dis[mi].X < dis[i].X))
            mi = i;
    return mi;
}

void solve() {
    /*memset(choose, 0, sizeof choose);
    memset(tag, 0, sizeof tag);
    memset(num, 0, sizeof num);
    memset(bound, 0, sizeof bound);
    memset(boss, 0, sizeof boss);
    memset(dis, 0, sizeof dis);
    memset(frm, 0, sizeof frm);
    memset(inq, 0, sizeof inq);
    memset(edges, 0, sizeof edges);
    for (int i = 0; i < 85; ++i)
        G[i].clear();*/
    int n, m, tp = 0, sum = 0, total = 0;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int k;
        cin >> k >> bound[i];
        bound[i] = k - bound[i];
        sum += bound[i];
        num[i] = 0;
        while (k--) {
            cin >> edges[tp].u >> edges[tp].v >> edges[tp].w;
            edges[tp].c = i, --edges[tp].u;
            choose[tp] = 0, total += edges[tp].w;
            ++tp;
        }
    }

    auto checkI1 = [&]() {
        return cal(n + 1, tp) == 1;
    };

    auto altI1 = [&](int rmv, int add) {
        assert((rmv == -1 || choose[rmv] == 1) && choose[add] == 0);
        if (rmv >= 0) choose[rmv] = 0;
        choose[add] = 1;
        int flag = checkI1();
        if (rmv >= 0) choose[rmv] = 1;
        choose[add] = 0;
        return flag;
    };

    auto altI2 = [&](int rmv, int add) {
        assert((rmv == -1 || choose[rmv] == 1) && choose[add] == 0);
        int f = num[edges[add].c] + 1;
        if (rmv >= 0 && edges[rmv].c == edges[add].c)
            --f;
        return f <= bound[edges[add].c];
    };

    auto flip = [&](int x) {
        if (choose[x]) --num[edges[x].c];
        else ++num[edges[x].c];
        assert(num[edges[x].c] <= bound[edges[x].c]);
        choose[x] ^= 1;
    };

    if (!checkI1()) {
        cout << "-1\n";
        return;
    }

    int cur = 0, ans = 0;
    while (cur < sum) {
        for (int i = 0; i < tp; ++i)
            G[i].clear();
        for (int i = 0; i < tp; ++i) {
            tag[i] = 0;
            if (!choose[i] && altI1(-1, i)) tag[i] |= 1;
            if (!choose[i] && altI2(-1, i)) tag[i] |= 2;
        }
        for (int i = 0; i < tp; ++i)
            if (choose[i])
                for (int j = 0; j < tp; ++j)
                    if (!choose[j]) {
                        if (altI1(i, j)) G[i].pb(j);
                        if (altI2(i, j)) G[j].pb(i);
                    }
        int res = SPFA(tp);
        if (res == -1) break;
        ans += dis[res].X;
        while (res != -1) {
            flip(res);
            res = frm[res];
        }
        ++cur;
    }
    if (cur < sum) cout << "-1\n";
    else cout << total - ans << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}