#include<bits/stdc++.h>
#define ll long long
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define pii pair<T,int>
using namespace std;
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ch=getchar();}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch^'0');
		ch=getchar();
	}
	return x;
}
int n,m,temp[1000002];
struct T{
	int l,r,v;
}q[1000002],p[1000002];
bool vis[1000002];
bool tp[1000002];
int k[1000002];
inline bool operator<(const T &x,const T &y){
	if(x.v!=y.v)return x.v<y.v;
	if(x.l!=y.l)return x.l<y.l;
	return x.r<y.r;
}
priority_queue<int>ins,del;
vector<int>upd[1000002];
#define mid ((l+r)>>1)
namespace seg{
	int tag[4000002],mmin[4000002];
	inline void pushup(int pos){
		mmin[pos]=min(mmin[pos<<1],mmin[pos<<1|1]);
	}
	inline void pushdown(int pos){
		if(tag[pos]){
			tag[pos<<1]+=tag[pos];
			tag[pos<<1|1]+=tag[pos];
			mmin[pos<<1]+=tag[pos];
			mmin[pos<<1|1]+=tag[pos];
			tag[pos]=0;
		}
	}
	inline void add(int pos,int l,int r,int ql,int qr){
		if(ql<=l&&qr>=r){
			++tag[pos];
			++mmin[pos];
			return;
		}
		pushdown(pos);
		if(ql<=mid)add(pos<<1,l,mid,ql,qr);
		if(qr>mid)add(pos<<1|1,mid+1,r,ql,qr);
		pushup(pos);
	}
	inline void add(int l,int r){//cerr<<"add "<<l<<" "<<r<<endl;
		if(r>0&&l<=m)add(1,1,m,l,r);
	}
	inline void mns(int pos,int l,int r,int ql,int qr){
		if(ql<=l&&qr>=r){
			--tag[pos];
			--mmin[pos];
			return;
		}
		pushdown(pos);
		if(ql<=mid)mns(pos<<1,l,mid,ql,qr);
		if(qr>mid)mns(pos<<1|1,mid+1,r,ql,qr);
		pushup(pos);
	}
	inline void mns(int l,int r){//cerr<<"mns "<<l<<" "<<r<<endl;
		if(r>0&&l<=m)mns(1,1,m,l,r);
	}
	inline int query(int pos,int l,int r,int ql,int qr){
		if(ql<=l&&qr>=r)return mmin[pos];
		pushdown(pos);
		if(ql<=mid&&qr>mid)return min(query(pos<<1,l,mid,ql,qr),query(pos<<1|1,mid+1,r,ql,qr));
		if(ql<=mid)return query(pos<<1,l,mid,ql,qr);
		return query(pos<<1|1,mid+1,r,ql,qr);
	}
}
ll ans;
vector<int>x[1000002];
bool flag;
int now;
inline void solve(int pos){//cerr<<pos<<" "<<q[now].v<<endl;
	while(q[now].v>pos)--now;
	if(q[now].v!=pos)return;
	int l=now;
	while(q[l-1].v==pos)--l;
	int mmin=INT_MAX;
	UF(i,now,l){
		int nxt=*lower_bound(x[pos].begin(),x[pos].end(),q[i].l);
		if(nxt>q[i].r){
			flag=false;
			return;
		}
		if(mmin>q[i].r){
			tp[nxt]=true;
			mmin=nxt;
		}
	}
}
int main(){
//	freopen("bubble.in","r",stdin);
//	freopen("bubble.out","w",stdout);
	F(iaknoi,1,read()){
		ins=del=priority_queue<int>();
		n=read();m=read();ans=0;
		F(i,1,n+1)upd[i].clear();
		F(i,1,m)x[i].clear();
		F(i,1,m<<2)seg::tag[i]=seg::mmin[i]=0;
		F(i,1,m)vis[i]=false;
		F(i,1,m){
			q[i].l=read();
			q[i].r=read();
			temp[i]=q[i].v=read();
		}
		sort(temp+1,temp+m+1);
		F(i,1,m)q[i].v=lower_bound(temp+1,temp+m+1,q[i].v)-temp;
		sort(q+1,q+m+1);
		q[0].v=q[m+1].v=-1;
		//F(i,1,m)cerr<<p[i].l<<" "<<p[i].r<<" "<<p[i].v<<endl;
		#define p q
		F(i,1,m){
			upd[p[i].l].push_back(i);
			upd[p[i].r+1].push_back(-i);
		}
		F(i,1,n){
			for(int x:upd[i]){
				if(x>0)ins.push(x);
				else del.push(-x);
			}
			while(del.size()&&ins.top()==del.top())ins.pop(),del.pop();
			if(ins.empty()){
				k[i]=1;
			}else{
				k[i]=p[ins.top()].v;
			}
			tp[i]=false;
			x[k[i]].push_back(i);
		}
		F(i,1,m)x[i].push_back(n+1);
		flag=true;
		now=m;
		UF(i,m,1)solve(i);
		if(!flag){puts("-1");continue;}
		UF(i,n,1){
			if(tp[i])seg::add(k[i]+1,m),ans+=seg::query(1,1,m,k[i],k[i]);
		}
		F(i,1,n){
			if(tp[i])seg::mns(k[i]+1,m),seg::add(1,k[i]-1);
			else{
				ans+=seg::query(1,1,m,k[i],m);
				seg::add(1,k[i]-1);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}