显然将权值离散化是没有问题的，因为必然存在一组最优解，满足每个 \(a_i\) 都取自于某个 \(V_i\)，于是不管三七二十一先将 \(V_i\) 离散化了再说。
考虑从部分分入手逐步分析这道题：
- 特殊性质 A：\(V_i=1\) 相当于这个区间中的数必须是 \(1\)，先将这些数去掉不管，紧接着考虑 \(V_i=0\) 的限制。我们贪心地想，对于每个区间，既然必须要有至少一个数是 \(0\)，那么我们肯定希望这个 \(0\) 越靠左越好，这样更有利于最小化逆序对个数。因此不难想到这样的策略：将所有 \(V_i=0\) 的区间按左端点从大到小排序，然后依次考虑每个区间，如果里面没有 \(0\) 就将最左边不是 \(1\) 的位置设成 \(0\)。如果找不到就 \(-1\)。这样还会有一些位置没有填，这些位置肯定一段前缀是 \(0\)，剩下是 \(1\)。直接枚举这个位置然后 \(O(1)\) 算答案即可。
- 特殊性质 B：限制相当于限制单点上的值。有限制的部分是容易计算的，考虑那些没有限制的部分，对于一个位置 \(i\)，我们记 \(v_{i,x}\) 表示令 \(a_i=x\) 的情况下，那些有限制的点与 \(i\) 构成的逆序对个数，然后我们发现，\(v_i\) 的 argmin 随着 \(i\) 的增加是不断增大的，这个容易用找最优解的过程得出，这样我们直接取 argmin 就是答案，因为这样没有限制的部分内部的逆序对个数是 \(0\)，也达到了最小。使用线段树维护之即可。
- 特殊性质 C：显然，我们会将每个区间的最小值摆在最左边的问题。后面的情况与特殊性质 B 类似，只不过有一个额外条件就是有个 \(a_i\ge lim_i\) 的限制。这时候我们大胆猜个结论：还是套用特殊性质 B 的做法，不过加上这个限制之后我们只能在 \(\ge lim_i\) 的部分找 argmin，如果有多个相同的则取最小的。正确性我不太会证明，不过感性理解一下就是，如果你比 argmin 更大那肯定不优，因为对于后面的位置而言肯定 \(a_i\) 越小越不容易产生逆序对，而如果比 argmin 小，那么我们将 \(a_i\) 与最优的 argmin 之间的所有位置都变为 argmin 是更优的。这样我们同样用线段树维护即可。
正解实际上是 A 与 C 的结合：即我们从大到小枚举 \(x\)，然后按左端点递减的顺序考虑所有 \(V_i=x\) 的区间，如果区间中没有 \(a_i=x\) 的位置就找到最左边没有被标记的位置，令其 \(a_i=x\)，找不到就 \(-1\)。处理完了之后把这些区间中所有位置都标记了。然后套用 C 的做法即可。前一半可以使用并查集的经典套路处理。这样复杂度就是 \(O(n\log n)\)。
const int MAXN=1e6;
int n,m,key[MAXN+5],uni[MAXN+5],num,lw[MAXN+5];
struct dat{int l,r,v;}a[MAXN+5];
vector<pii>vec[MAXN+5];
vector<int>ins[MAXN+5],del[MAXN+5];
int f[MAXN+5],nd[MAXN+5];
int find(int x){return (!f[x])?x:f[x]=find(f[x]);}
void clear(){
num=0;
for(int i=1;i<=n;i++)nd[i]=0;
for(int i=1;i<=n+1;i++)ins[i].clear(),del[i].clear();
for(int i=1;i<=m;i++)vec[i].clear();
for(int i=1;i<=n+1;i++)f[i]=0;
}
struct node{int l,r,lz;pii mn;}s[MAXN*4+5];
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;s[k].lz=0;s[k].mn=mp(0,l);if(l==r)return;
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void tag(int k,int v){s[k].lz+=v;s[k].mn.fi+=v;}
void pushdown(int k){if(s[k].lz)tag(k<<1,s[k].lz),tag(k<<1|1,s[k].lz),s[k].lz=0;}
void modify(int k,int l,int r,int v){
if(l>r)return;if(l<=s[k].l&&s[k].r<=r)return tag(k,v),void();
pushdown(k);int mid=s[k].l+s[k].r>>1;
if(r<=mid)modify(k<<1,l,r,v);else if(l>mid)modify(k<<1|1,l,r,v);
else modify(k<<1,l,mid,v),modify(k<<1|1,mid+1,r,v);
s[k].mn=min(s[k<<1].mn,s[k<<1|1].mn);
}
pii query(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r)return s[k].mn;pushdown(k);
int mid=s[k].l+s[k].r>>1;
if(r<=mid)return query(k<<1,l,r);else if(l>mid)return query(k<<1|1,l,r);
else return min(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
}
struct fenwick{
int t[MAXN+5];
void init(){for(int i=1;i<=num;i++)t[i]=0;}
void add(int x,int v){for(int i=x;i<=num;i+=(i&(-i)))t[i]+=v;}
int query(int x){int ret=0;for(int i=x;i;i&=(i-1))ret+=t[i];return ret;}
}T;
void solve(){
scanf("%d%d",&n,&m);clear();
for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v),key[i]=a[i].v;
for(int i=1;i<=m;i++)key[i]=a[i].v;sort(key+1,key+m+1);key[0]=-1;
for(int i=1;i<=m;i++)if(key[i]!=key[i-1])uni[++num]=key[i];
for(int i=1;i<=m;i++)a[i].v=lower_bound(uni+1,uni+num+1,a[i].v)-uni;
for(int i=1;i<=m;i++)vec[a[i].v].pb(mp(a[i].l,a[i].r));
for(int i=1;i<=m;i++)ins[a[i].l].pb(a[i].v),del[a[i].r+1].pb(a[i].v);
multiset<int>st;
for(int i=1;i<=n;i++){
for(int x:ins[i])st.insert(x);
for(int x:del[i])st.erase(st.find(x));
lw[i]=(st.empty())?1:(*st.rbegin());
}
for(int i=num;i;i--){
sort(vec[i].begin(),vec[i].end(),[&](pii p1,pii p2){return p1.fi>p2.fi;});
int lst=0;
for(pii p:vec[i]){
if(p.fi<=lst&&lst<=p.se)continue;
int pos=find(p.fi);
if(pos>p.se)return puts("-1"),void();
nd[pos]=i;lst=pos;
}
for(pii p:vec[i]){
while(1){
int x=find(p.fi);
if(x>p.se)break;f[x]=x+1;
}
}
}
build(1,1,num);
for(int i=1;i<=n;i++)if(nd[i])modify(1,nd[i]+1,num,1);
// for(int i=1;i<=n;i++)printf("%d%c",nd[i]," \n"[i==n]);
for(int i=1;i<=n;i++){
if(nd[i])modify(1,nd[i]+1,num,-1),modify(1,1,nd[i]-1,1);
else{
int pos=query(1,lw[i],num).se;
nd[i]=pos;modify(1,1,nd[i]-1,1);
}
}
T.init();ll res=0;
for(int i=1;i<=n;i++)res+=i-1-T.query(nd[i]),T.add(nd[i],1);
printf("%lld\n",res);
}
int main(){
int qu;scanf("%d",&qu);
while(qu--)solve();
return 0;
}