#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define db double
#define ve vector<int>
#define pa pair<int,int>
#define fr first
#define sd second
#define pb push_back
#define mp make_pair
#define MEM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
#define N 1000010
int n, m;
int l[N], r[N], v[N];
int p[N], cnt, mx[N], w[N];
vector<pair<int, int>>qr[N];
vector<int>pos[N];
namespace Tree1
{
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
int tag[N << 2];
void build(int l, int r, int x)
{
	tag[x] = 1;
	if (l == r)return ;
	build(l, mid, ls); build(mid + 1, r, rs);
}
void add(int l, int r, int x, int ql, int qr, int w)
{
	if (l == ql && r == qr) {tag[x] = max(tag[x], w); return ;}
	if (qr <= mid)add(l, mid, ls, ql, qr, w);
	else if (ql > mid)add(mid + 1, r, rs, ql, qr, w);
	else add(l, mid, ls, ql, mid, w), add(mid + 1, r, rs, mid + 1, qr, w);
}
void sol(int l, int r, int x, int v)
{
	v = max(v, tag[x]);
	if (l == r) {mx[l] = v; return ;}
	sol(l, mid, ls, v); sol(mid + 1, r, rs, v);
}
#undef ls
#undef rs
#undef mid
}
namespace Tree2
{
int minn[N << 2], tag[N << 2], id[N << 2];
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
void pushup(int x)
{
	minn[x] = min(minn[ls], minn[rs]);
	if (minn[ls] == minn[x])id[x] = id[ls];
	else id[x] = id[rs];
}
void push(int x, int w) {tag[x] += w; minn[x] += w;}
void pushdown(int x) {if (tag[x]) {push(ls, tag[x]); push(rs, tag[x]); tag[x] = 0;}}
void build(int l, int r, int x)
{
	minn[x] = tag[x] = 0;
	if (l == r) {id[x] = l; return ;}
	build(l, mid, ls); build(mid + 1, r, rs);
	pushup(x);
}
void add(int l, int r, int x, int ql, int qr, int w)
{
	if (ql > qr)return ;
	if (l == ql && r == qr) {push(x, w); return ;}
	pushdown(x);
	if (qr <= mid)add(l, mid, ls, ql, qr, w);
	else if (ql > mid)add(mid + 1, r, rs, ql, qr, w);
	else add(l, mid, ls, ql, mid, w), add(mid + 1, r, rs, mid + 1, qr, w);
	pushup(x);
}
pair<int, int>qry(int l, int r, int x, int ql, int qr)
{
	if (l == ql && r == qr) {return {minn[x], id[x]};}
	pushdown(x);
	if (qr <= mid)return qry(l, mid, ls, ql, qr);
	else if (ql > mid)return qry(mid + 1, r, rs, ql, qr);
	else
	{
		auto p = qry(l, mid, ls, ql, mid), q = qry(mid + 1, r, rs, mid + 1, qr);
		if (p.fr <= q.fr)return p;
		else return q;
	}
}
}
int c[N];
void add(int x) {for (; x <= cnt; x += x & (-x))c[x] ++;}
int qry(int x) {int s = 0; for (; x; x -= x & (-x))s += c[x]; return s;}
void clear()
{
	for (int i = 1; i <= cnt; i ++)qr[i].clear(), pos[i].clear(), c[i] = 0;
	cnt = 0;
}
ll calc(const vector<int>v)
{
	ll s = 0;
	for (int x : v) {s += qry(cnt) - qry(x); add(x);}
	for (int i = 1; i <= cnt; i ++)c[i] = 0;
	return s;
}

void init()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i ++)
	{
		cin >> l[i] >> r[i] >> v[i];
		p[++ cnt] = v[i];
	}
	p[++ cnt] = 0;
	sort(p + 1, p + cnt + 1); cnt = unique(p + 1, p + cnt + 1) - p - 1;
	for (int i = 1; i <= m; i ++)v[i] = lower_bound(p + 1, p + cnt + 1, v[i]) - p;
}
void sol()
{
	init();
	Tree1 :: build(1, n, 1);
	for (int i = 1; i <= m; i ++)Tree1 :: add(1, n, 1, l[i], r[i], v[i]);
	Tree1 :: sol(1, n, 1, 1);
	for (int i = 1; i <= n; i ++)pos[mx[i]].push_back(i);
	for (int i = 1; i <= m; i ++)qr[v[i]].push_back({l[i], r[i]});
	for (int i = 1; i <= n; i ++)w[i] = -1;
	set<int>S = {0, n + 1};
	int flag = 0;
	for (int i = 1; i <= cnt; i ++)
	{
		for (int x : pos[i])S.insert(x);
		sort(qr[i].begin(), qr[i].end()); reverse(qr[i].begin(), qr[i].end());
		int lst = n + 1;
		for (auto [l, r] : qr[i])
		{
			if (lst <= r)continue;
			int t = (*S.lower_bound(l));
			// cout << "WTF:" << l << ' ' << r << ' ' << t << endl;
			if (t > r) {flag = 1; break;}
			else w[t] = i, lst = t;
		}
	}
	if (flag) {cout << "-1\n"; clear(); return ;}
	Tree2 :: build(1, cnt, 1);
	ll ans = 0;
	vector<int>v;
	// for (int i = 1; i <= n; i ++)cout << w[i] << ' '; cout << endl;
	// for (int i = 1; i <= n; i ++)cout << mx[i] << ' '; cout << endl;
	for (int i = 1; i <= n; i ++)if (w[i] != -1)
		{
			Tree2 :: add(1, cnt, 1, w[i] + 1, cnt, 1);
			v.push_back(w[i]);
		}
	ans = calc(v);
	// cout << "GG:" << ans << " " << calc({2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2}) << endl;
	for (int i = 1; i <= n; i ++)
	{
		if (w[i] != -1)
		{
			Tree2 :: add(1, cnt, 1, w[i] + 1, cnt, -1);
			Tree2 :: add(1, cnt, 1, 1, w[i] - 1, +1);
			continue;
		}
		auto tmp = Tree2 :: qry(1, cnt, 1, mx[i], cnt);
		ans += tmp.fr; w[i] = tmp.sd;
		// cout << "GG:" << mx[i] << ' ' << w[i] << " " << tmp.fr << " " << Tree2 :: qry(1, cnt, 1, 1, 1).fr << ' ' << Tree2 :: qry(1, cnt, 1, 2, 2).fr << endl;
		Tree2 :: add(1, cnt, 1, 1, w[i] - 1, + 1);
	}
	// for (int i = 1; i <= n; i ++)cout << w[i] << ','; cout << endl;
	cout << ans << '\n';
	clear();
}
signed main()
{
	// freopen("bubble.in","r",stdin);
	// freopen("bubble.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T; cin >> T;
	while (T --)sol();
	return 0;
}