// vscode automatically formatted my code wtf

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void OJize()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
}

namespace easylib
{
#define sz(X) (int)((X).size())
#define entire(X) X.begin(), X.end()
	const int IINF = 0x3f3f3f3f;
	const ll LINF = 0x3f3f3f3f3f3f3f3f;
	// Input
	template <class T1, class T2>
	istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second; }
	template <class T>
	istream &operator>>(istream &is, vector<T> &V)
	{
		for (auto &x : V)
			is >> x;
		return is;
	}

	// Output (mostly just for debugging)
	template <class T1, class T2>
	ostream &operator<<(ostream &os, pair<T1, T2> const &x)
	{
		os << '(' << x.first << ", " << x.second << ')';
		return os;
	}
	template <class Ch, class Tr, class Container>
	basic_ostream<Ch, Tr> &operator<<(basic_ostream<Ch, Tr> &os, Container const &x)
	{
		os << "[ ";
		for (auto &y : x)
			os << y << " ";
		return os << "]";
	}
}
using namespace easylib;

template <typename T, typename MAT1, typename MAT2>
pair<vector<T>, vector<vector<int>>>
matroid_intersection(int n, MAT1 &A, MAT2 &B, vector<T> weight)
{
	assert(A.n == n && B.n == n && sz(weight) == n);
	A.init(), B.init();
	vector<bool> I(n);

	// https://justicehui.github.io/icpc/2021/09/08/BOJ16046/
	vector<vector<pair<int, T>>> G(n + 2);
	T max_w = 1;
	for (T w : weight)
		max_w = max(max_w, abs(w) + 1);
	auto spfa = [&](int s, int t)
	{
		vector<bool> queued(n + 2);
		queued[s] = true;
		vector<int> prv(n + 2, -1);
		vector<T> dist(n + 2, max_w * (max_w + 1) * n);
		dist[s] = 0;
		queue<int> Q({s});
		while (!Q.empty())
		{
			int v = Q.front();
			Q.pop();
			queued[v] = false;
			for (auto [u, cost] : G[v])
				if (dist[u] > dist[v] + cost)
				{
					dist[u] = dist[v] + cost, prv[u] = v;
					if (!queued[u])
						queued[u], Q.push(u);
				}
		}
		if (prv[t] == -1)
			return false;
		for (int i = t; i != s; i = prv[i])
			if (i < n)
				I[i] = !I[i];
		return true;
	};

	auto augment = [&]()
	{
		for (auto &row : G)
			row.clear();
		for (int i = 0; i < n; i++)
		{
			A.init();
			B.init();
			for (int k = 0; k < n; k++)
				if (i != k && I[k])
					A.add(k), B.add(k);
			if (!I[i])
			{
				if (A.check(i))
					G[n].push_back({i, weight[i] * max_w + 1});
				if (B.check(i))
					G[i].push_back({n + 1, -1});
			}
			else
				for (int j = 0; j < n; j++)
					if (!I[j])
					{
						if (A.check(j))
							G[i].push_back({j, weight[j] * max_w + 1});
						if (B.check(j))
							G[j].push_back({i, -weight[i] * max_w + 1});
					}
		}
		return spfa(n, n + 1);
	};

	vector<T> ans_cost;
	vector<vector<int>> ans_I;
	while (augment())
	{
		T cost = 0;
		vector<int> use;
		for (int i = 0; i < n; i++)
			if (I[i])
				cost += weight[i], use.push_back(i);
		ans_cost.push_back(cost);
		ans_I.push_back(use);
	}
	return {ans_cost, ans_I};
}

// Colorful matroid
struct ColorfulMat
{
	int n;
	// matroid-specific vars
	int v;
	vector<int> col, deg, avail;

	ColorfulMat(vector<int> COL, vector<int> DEG) : n(sz(COL)), v(sz(deg)), col(COL), deg(DEG), avail(DEG) { init(); }
	void init() { avail = deg; }
	void add(int i) { avail[col[i]]--; }
	bool check(int i) { return avail[col[i]] > 0; }
};

// Cographic matroid
struct CographicMat
{
	int n;
	// matroid-specific vars
	vector<int> par;
	vector<pair<int, int>> ed;
	vector<bool> chosen;
	void merge(int x, int y) { par[find(x)] = find(y); } // yr becomes parent
	int find(int x) { return par[x] != x ? (par[x] = find(par[x])) : x; }

	CographicMat(vector<pair<int, int>> ED, int V) : n(sz(ED)), par(V), ed(ED) {}
	void init() { chosen = vector<bool>(n); }
	void add(int i) { chosen[i] = true; }
	bool check(int i)
	{
		iota(entire(par), 0);
		for (int z = 0; z < n; z++)
			if (!chosen[z] && z != i)
			{
				auto [a, b] = ed[z];
				merge(a, b);
			}
		for (int v = 1; v < sz(par); v++)
			if (find(0) != find(v))
			{
				return false;
			}
		return true;
	}
};

int main()
{
	OJize();
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n, npc;
		cin >> n >> npc;
		int whole_weight = 0, leeway = 0;
		vector<int> COL, DEG, WEIGHT;
		vector<pair<int, int>> ED;
		for (int npcid = 0; npcid < npc; npcid++)
		{
			int num_hint, req;
			cin >> num_hint >> req;
			for (int zz = 0; zz < num_hint; zz++)
				COL.push_back(npcid);
			DEG.push_back(num_hint - req);
			leeway += num_hint - req;
			while (num_hint--)
			{
				int a, b, w;
				cin >> a >> b >> w;
				ED.push_back({a - 1, b});
				whole_weight += w;
				WEIGHT.push_back(-w);
			}
		}

		auto mat1 = ColorfulMat(COL, DEG);
		auto mat2 = CographicMat(ED, n + 1);
		auto sol = matroid_intersection(sz(COL), mat1, mat2, WEIGHT).first;

		if(sol.empty()){cout<<"-1\n";}
		else
			cout << whole_weight + sol.back() << '\n';
	}
}