#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6,inf=1e9;
int n,m,mus[N+5],lef[N+5],L[N+5],R[N+5],X[N+5],b[N+5],c[N+5],pl[N+5];
int tag[4*N+5],mn[4*N+5],mnp[4*N+5],fa[N+5];
void U(int x){
	while(x<=m)c[x]++,x+=x&-x;
}
int Q(int x){
	int r=0;
	while(x)r+=c[x],x-=x&-x;
	return r;
}
void Pushup(int p){
	if(mn[p*2]<=mn[p*2+1])mn[p]=mn[p*2],mnp[p]=mnp[p*2];
	else mn[p]=mn[p*2+1],mnp[p]=mnp[p*2+1];
}
void Build(int p,int l,int r){
	tag[p]=0;
	if(l==r)return mn[p]=0,mnp[p]=l,void();
	int mid=(l+r)/2;
	Build(p*2,l,mid),Build(p*2+1,mid+1,r),Pushup(p);
}
void Tag(int p,ll z){
	tag[p]+=z,mn[p]+=z;
}
void Pushdown(int p){
	if(tag[p])Tag(p*2,tag[p]),Tag(p*2+1,tag[p]),tag[p]=0;
}
void Add(int p,int l,int r,int x,int y,ll z){
	if(x<=l&&r<=y)return Tag(p,z);
	int mid=(l+r)>>1;
	Pushdown(p);
	if(x<=mid)Add(p*2,l,mid,x,y,z);
	if(mid<y)Add(p*2+1,mid+1,r,x,y,z);
	Pushup(p);
}
int M,MP;
void Get(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		if(mn[p]<M)M=mn[p],MP=mnp[p];
		return ;
	}
	int mid=(l+r)>>1;
	Pushdown(p);
	if(x<=mid)Get(p*2,l,mid,x,y);
	if(mid<y)Get(p*2+1,mid+1,r,x,y);
}
void Clear(){
	for(int i=0;i<=max(n,m);i++)mus[i]=lef[i]=b[i]=c[i]=0;
}
int gf(int x){
	return x==fa[x]?x:fa[x]=gf(fa[x]);
}
void Solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&L[i],&R[i],&X[i]),b[i]=X[i];
	sort(b+1,b+m+1),Build(1,1,m);
	fill(lef+1,lef+n+1,1);
	for(int i=1;i<=m;i++)pl[i]=i,X[i]=lower_bound(b+1,b+m+1,X[i])-b;
	for(int i=1;i<=n+1;i++)fa[i]=i;
	sort(pl+1,pl+m+1,[](int x,int y){
		if(X[x]!=X[y])return X[x]>X[y];
		return L[x]>L[y];
	});
	for(int i=1,j;i<=m;i=j+1){
		j=i;
		while(j<m&&X[pl[j+1]]==X[pl[i]])j++;
		for(int k=i,lst=n+1;k<=j;k++){
			int id=pl[k];
			if(lst<=R[id])continue;
			int o=gf(L[id]);
			if(o>R[id])return puts("-1"),Clear();
			mus[lst=o]=X[id];
			if(X[id]<m)Add(1,1,m,X[id]+1,m,1);
		}
		for(int k=i;k<=j;k++){
			int id=pl[k];
			while(1){
				int o=gf(L[id]);
				if(o>R[id])break;
				lef[o]=X[id],fa[o]=o+1;
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(mus[i]){
			if(mus[i]<m)Add(1,1,m,mus[i]+1,m,-1);
			if(mus[i]>1)Add(1,1,m,1,mus[i]-1,1);
		}
		else {
			M=MP=inf,Get(1,1,m,lef[i],m),mus[i]=MP;
			if(mus[i]>1)Add(1,1,m,1,mus[i]-1,1);
		}
		ans+=i-1-Q(mus[i]),U(mus[i]);
	}
	cout<<ans<<'\n',Clear();
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--)Solve();
}