#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 100;
constexpr int inf = 1E9;

int f[N];

void init(int n) {
    std::iota(f, f + n, 0);
}

int find(int x) {
    while (x != f[x]) {
        x = f[x] = f[f[x]];
    }
    return x;
}

int merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) {
        return 0;
    }
    f[b] = a;
    return 1;
}

void solve() {
    int n, m;
    std::cin >> n >> m;
    n += 1;
    
    std::vector<std::array<int, 4>> edges;
    std::vector<int> k(m);
    int C = 0;
    init(n);
    for (int i = 0; i < m; i++) {
        int c;
        std::cin >> c >> k[i];
        k[i] = c - k[i];

        for (int j = 0; j < c; j++) {
            int x, y, w;
            std::cin >> x >> y >> w;
            x--;
            C += merge(x, y);
            edges.push_back({x, y, w, i});
        }
    }
    if (C != n - 1) {
        std::cout << -1 << "\n";
        return;
    }

    int l = edges.size();
    std::vector<int> in(l);

    while (true) {
        std::vector<int> cnt(m);
        for (int i = 0; i < l; i++) {
            if (in[i]) {
                cnt[edges[i][3]] += 1;
            }
        }
        
        std::vector<int> f1(l), f2(l);
        for (int i = 0; i < l; i++) {
            if (!in[i]) {
                int j = edges[i][3];
                f1[i] = cnt[j] < k[j];
                init(n);
                int c = 0;
                for (int j = 0; j < l; j++) {
                    if (!in[j] && j != i) {
                        c += merge(edges[j][0], edges[j][1]);
                    }
                }
                f2[i] = (c == n - 1);
            }
        }

        std::vector g(l, std::vector<int>(l));
        for (int i = 0; i < l; i++) {
            if (in[i]) {
                for (int j = 0; j < l; j++) {
                    if (!in[j]) {
                        int u = edges[j][3];
                        g[i][j] = (cnt[u] + 1 - (edges[i][3] == u) <= k[u]);

                        init(n);
                        int c = 0;
                        for (int k = 0; k < l; k++) {
                            if ((!in[k] && k != j) || k == i) {
                                c += merge(edges[k][0], edges[k][1]);
                            }
                        }
                        g[j][i] = (c == n - 1);
                    }
                }
            }
        }

        std::queue<int> q;
        std::vector<int> inq(l), prv(l, -1);
        std::vector<std::pair<int, int>> dis(n, {-inf, -inf});
        for (int i = 0; i < l; i++) {
            if (f1[i]) {
                dis[i] = {edges[i][2], 0};
                q.push(i);
                inq[i] = 1;
            }
        }

        int t = -1;
        while (!q.empty()) {
            int x = q.front();
            q.pop();

            if (f2[x] && (t == -1 || dis[x] > dis[t])) {
                t = x;
            }
            inq[x] = 0;

            for (int y = 0; y < l; y++) {
                if (g[x][y]) {
                    std::pair<int, int> ndis = {dis[x].first + (in[y] ? -1 : 1) * edges[y][2], dis[x].second - 1};
                    if (ndis > dis[y]) {
                        dis[y] = ndis;
                        prv[y] = x;
                        if (!inq[y]) {
                            q.push(y);
                            inq[y] = 1;
                        }
                    }
                }
            }
        }
        if (t == -1) {
            break;
        }

        for (int i = t; i != -1; i = prv[i]) {
            in[i] ^= 1;
        }
    }

    int tot = std::count(in.begin(), in.end(), 1);

    if (tot != std::accumulate(k.begin(), k.end(), 0)) {
        std::cout << -1 << "\n";
    } else {
        i64 sum = 0;
        for (int i = 0; i < l; i++) {
            if (!in[i]) {
                sum += edges[i][2];
            }
        }
        std::cout << sum << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}