#include<bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;

pii operator +(const pii &a,const pii &b)
{
    return {a.first+b.first,a.second+b.second};
}

const int N=82;

int T,n,m,c[N],k[N],u[N],v[N],w[N],e[N],E;

vector<int> cho;

int fa[N];

int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

bool chk1(vector<int> cho)
{
    for(int j=0;j<=n;j++)
        fa[j]=j;
    int C=n+1;
    for(int j=1;j<=E;j++)
        if(!cho[j])
        {
            int x=u[j],y=v[j];
            if(find(x)!=find(y))
                fa[find(x)]=find(y),C--;
        }
    return C==1;
}

bool chk2(vector<int> cho)
{
    vector<int> cnt(m+1);
    for(int i=1;i<=E;i++)
        if(cho[i])
            cnt[e[i]]++;
    for(int i=1;i<=m;i++)
        if(cnt[i]>c[i]-k[i])
            return 0;
    return 1;
}

vector<int> g[N];

int W[N];

pii d[N];

int inq[N],pre[N];

int main()
{
    srand(time(NULL));
    scanf("%d",&T);
    while(T--)
    {
        // if(T==8)
        //     break;
        E=0;
        
        scanf("%d%d",&n,&m);
        // n=20,m=20;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&c[i],&k[i]);
            // c[i]=4;
            // k[i]=rand()%4;
            for(int j=1;j<=c[i];j++)
            {
                ++E;
                // u[E]=rand()%n+1;
                // v[E]=rand()%n+1;
                // if(u[E]>v[E])
                //     swap(u[E],v[E]);
                // w[E]=rand()%10;
                scanf("%d%d%d",&u[E],&v[E],&w[E]);
                u[E]--;
                e[E]=i;
            }
        }
        cho.clear();
        cho.resize(E+1);
        if(!chk1(cho))
        {
            puts("-1");
            continue;
        }
        while(1)
        {
            // assert(chk1(cho));
            // assert(chk2(cho));
            vector<int> X,Y;
            for(int i=1;i<=E;i++)
                if(!cho[i])
                {
                    auto nc=cho;
                    nc[i]=1;
                    if(chk1(nc))
                        X.push_back(i);
                    if(chk2(nc))
                        Y.push_back(i);
                }
            for(int i=1;i<=E;i++)
                g[i].clear();
            for(int i=1;i<=E;i++)
                W[i]=cho[i]?-w[i]:w[i];
            for(int i=1;i<=E;i++)
                if(!cho[i])
                {
                    auto nc=cho;
                    nc[i]^=1;
                    for(int j=1;j<=E;j++)
                        if(cho[j])
                        {
                            nc[j]^=1;
                            if(chk2(nc))
                                g[i].push_back(j);
                            if(chk1(nc))
                                g[j].push_back(i);
                            nc[j]^=1;
                        }
                }
            for(int i=1;i<=E;i++)
                d[i]={-1e9,-1e9},inq[i]=0,pre[i]=0;
            queue<int> q;
            for(auto x:X)
                d[x]={W[x],-1},q.push(x),pre[x]=x,inq[x]=1;
            while(!q.empty())   
            {
                int x=q.front();
                q.pop();
                inq[x]=0;
                for(auto v:g[x])
                {
                    if(d[v]<d[x]+pii(W[v],-1))
                    {
                        d[v]=d[x]+pii(W[v],-1);
                        pre[v]=x;
                        if(!inq[v])
                            q.push(v),inq[v]=1;
                    }
                }
            }
            int p=-1;
            for(auto y:Y)
                if(p==-1||d[y]>d[p])
                    p=y;
            if(p==-1||d[p].second<-1e8)
                break;
            int sm=0,t=p;
            while(1)
            {
                cho[t]^=1;
                if(t==pre[t])
                    break;
                t=pre[t];
            }
        }
        vector<int> cnt(m+1);
        for(int i=1;i<=E;i++)
            if(cho[i])
                cnt[e[i]]++;
        bool ok=1;
        for(int i=1;i<=m;i++)
            if(cnt[i]!=c[i]-k[i])
                ok=0;
        int sw=0;
        for(int i=1;i<=E;i++)
            if(!cho[i])
                sw+=w[i];
        if(!ok)
            puts("-1");
        else
            printf("%d\n",sw);
    }
}