#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		vector<int> k(m+5),c(m+5);
		vector<tuple<int,int,int,int>> a(111);//u,v,c,w
		int sum=0;
		long long ans=0;
		int idx=0;
		for(int i=1;i<=m;i++)
		{
			cin>>k[i]>>c[i];
			sum+=k[i]-c[i];
			for(int j=1;j<=k[i];j++)
			{
				int l,r,w;
				cin>>l>>r>>w;
				a[++idx]={l,r+1,i,w};
				ans+=w;
			}
		}
		vector<int> in(idx+5);
		auto connected=[&]()
		{
//			cerr<<"check connected: "<<endl;
			vector<int> pa(n+5);
			function<int(int)> find=[&](int x){return pa[x]?pa[x]=find(pa[x]):x;};
			int cc=n+1;
			for(int i=1;i<=idx;i++)
			{
				if(not in[i])
				{
//					cerr<<"addedge "<<i<<endl;
					auto [u,v,col,w]=a[i];
					int pu=find(u),pv=find(v);
					if(pu!=pv)
					{
						pa[pv]=pu;
						cc--;
					}
				}
			}
//			cerr<<cc<<endl;
			return cc==1;
		};
		vector<int> cnt(m+5);
		for(int i=1;i<=m;i++)
			cnt[i]=k[i];
		for(int tt=1;tt<=sum;tt++)
		{
//			cerr<<"round "<<tt<<endl;
			vector<vector<int>> G(idx+5);
			vector<int> w(idx+5),good1(idx+5),good2(idx+5);
			for(int i=1;i<=idx;i++)
			{
				if(not in[i])
				{
					in[i]=1;
					if(connected())good1[i]=1;
					for(int j=1;j<=idx;j++)
					{
						if(i!=j and in[j])
						{
							in[j]=0;
							if(connected())G[j].push_back(i);
							in[j]=1;
						}
					}
					in[i]=0;
					int ci=get<2>(a[i]);
					if(cnt[ci]>c[ci])good2[i]=1;
					if(cnt[ci]>=c[ci])
					{
						for(int j=1;j<=idx;j++)
						{
							if(i!=j and in[j] and get<2>(a[j])==ci)
								G[i].push_back(j);
						}
					}
					w[i]=-get<3>(a[i]);
				}
				else w[i]=get<3>(a[i]);
			}
//			for(int i=1;i<=m;i++)cerr<<"col "<<i<<' '<<cnt[i]<<endl;
//			for(int i=1;i<=idx;i++)cerr<<"E "<<get<0>(a[i])<<' '<<get<1>(a[i])<<' '<<get<2>(a[i])<<' '<<get<3>(a[i])<<endl;
//			for(int i=1;i<=idx;i++)
//			{
//				cerr<<i<<' '<<in[i]<<' '<<good1[i]<<' '<<good2[i]<<endl;
//				for(auto v:G[i])
//					cerr<<"edge "<<i<<' '<<v<<endl;
//			}
			//spfa
			vector<int> dis(idx+5,1e9),las(idx+5);
			vector<int> inq(idx+5);
			queue<int> q;
			for(int i=1;i<=idx;i++)
			{
				if(good1[i])
				{
					dis[i]=w[i];
					inq[i]=1;
					q.push(i);
				}
			}
			while(not q.empty())
			{
				int u=q.front();q.pop();
				inq[u]=0;
				for(auto v:G[u])
				{
					if(dis[v]>dis[u]+w[v])
					{
						dis[v]=dis[u]+w[v];
						las[v]=u;
						if(not inq[v])q.push(v),inq[v]=1;
					}
				}
			}
			int mindis=1e9,minpos=0;
			for(int i=1;i<=idx;i++)
			{
				if(good2[i] and dis[i]<mindis)
				{
					mindis=dis[i];
					minpos=i;
				}
			}
//			cerr<<"mindis: "<<mindis<<endl;
			if(mindis==1e9)
			{
				ans=-1;
				break;
			}
			//output solution,flip in[],update cnt[]
			int u=minpos;
			while(not good1[u])
			{
//				cerr<<"flip "<<u<<endl;
				if(in[u])
				{
					cnt[get<2>(a[u])]++;
					in[u]=0;
				}
				else
				{
					cnt[get<2>(a[u])]--;
					in[u]=1;
				}
				u=las[u];
			}
//			cerr<<"flip2 "<<u<<endl;
			if(in[u])
			{
				cnt[get<2>(a[u])]++;
				in[u]=0;
			}
			else
			{
				cnt[get<2>(a[u])]--;
				in[u]=1;
			}
			ans+=mindis;
		}
		if(not connected())ans=-1;
		cout<<ans<<endl;
	}
	return 0;
}