写了个假算，没想到过了

感觉很难 hack？？？

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=6e6+7;
int T,n,m;
map<int,map<int,int> >mp;
map<int,int>num,val,sh;
int c[Maxn],cid;
int f[Maxn];
struct node{
	int u,v,w;
	inline friend bool operator <(node x,node y){
		return x.w<y.w;
	}
}E[Maxn],G[Maxn];
int tot,pp;

int qfind(int key){
	return key==f[key]?key:f[key]=qfind(f[key]);
}
void Merge(int u,int v){
	int qu=qfind(u),qv=qfind(v);
	if(qu==qv) return ;
	f[qu]=qv;
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		tot=0;
		mp.clear();
		num.clear();
		sh.clear();
		cid=0;
		pp=0;

		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			mp[u][v]=w;
			mp[v][u]=w;
			num[u]=num[v]=1;
			G[++pp]=(node){u,v,w};
		}
		
		int lst=0;
		ll ans=0;
		for(auto I:num){
			int i=I.first;
			if(i-lst>1){
				c[++cid]=i-1;
				ans+=i-1-lst-1;
			}
			c[++cid]=i;
			
			lst=i;
		}
		if(lst<n) c[++cid]=n,ans+=n-lst-1;
		for(int i=1;i<=cid;i++) f[i]=i,sh[c[i]]=i;
		for(int i=1;i<=pp;i++){
			int u=G[i].u,v=G[i].v,w=G[i].w;
			E[++tot]=(node){sh[u],sh[v],w};
		}
		sort(c+1,c+cid+1);
		for(int i=1;i<=cid;i++){
            int cpp=0;
			for(int j=i+1;j<=cid;j++){
				if(mp[c[i]][c[j]]){
					continue;
				}
				cpp++;
				E[++tot]=(node){i,j,j-i};
                mp[c[i]][c[j]]=1;
                mp[c[j]][c[i]]=1;
				if(cpp>=5)break;
			}
            cpp=0;
			for(int j=i-1;j;j--){
				if(mp[c[i]][c[j]]){
					continue;
				}
				E[++tot]=(node){i,j,i-j};
                mp[c[i]][c[j]]=1;
                mp[c[j]][c[i]]=1;
                cpp++;
				if(cpp>=5)break;
			}
		}

		sort(E+1,E+tot+1);
		for(int i=1;i<=tot;i++){
			int u=E[i].u,v=E[i].v,w=E[i].w;	
			if(qfind(u)!=qfind(v)){
				Merge(u,v);
				ans+=w;
			}
		}
		printf("%lld\n",ans);
		
	}

	return 0;
}
/*
3
5 3
1 2 5
2 3 4
1 5 0
5 0
5 4
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
*/