用树链剖分写的，WA on #7,求大佬看看qwq

#include<bits/stdc++.h>
using namespace std;
const long long NUM=2e6;
long long N,M,ans_min;
long long fa[NUM];
long long getfa(long long x)//并查集
{
	if(x==fa[x]) return x;
	return fa[x]=getfa(fa[x]);
}
struct line//存储题目给的所有边
{
	long long f,t,w;
}l[NUM];
queue<line> q;//存储不在最小生成树中的边
bool cmp(line a,line b)
{
	return a.w<b.w;
}
struct road//存储在最小生成树中的所有边
{
	long long next,to,w;
}r[NUM];
struct point
{
	long long head,w,depth,size,son,top,father,id;
}po[NUM],pn[NUM];
long long cnt_road;
void add(long long f,long long t,long long w)
{
	r[++cnt_road].to=t;
	r[cnt_road].next=po[f].head;
	r[cnt_road].w=w;
	po[f].head=cnt_road;
}
//以下为树链剖分
bool vis1[NUM];
long long fl;
void dfs1(long long x)
{
	vis1[x]=1;
	po[x].size=po[x].depth=++fl;
	for(long long i=po[x].head;i;i=r[i].next)
	{
		if(vis1[r[i].to]) continue;
		po[r[i].to].w=r[i].w;
		dfs1(r[i].to);
		if(po[r[i].to].size>po[x].size)
		{
			po[x].size=po[r[i].to].size;
			po[x].son=r[i].to;
		}
	}
	fl--;
}
bool vis2[NUM];
long long new_id;
void dfs2(long long x)
{
	vis2[x]=1;
	pn[++new_id]=po[x];
	po[x].id=new_id;
	if(!po[x].son) return ;
	long long me=new_id;
	po[po[x].son].top=po[x].top;
	dfs2(po[x].son);
	for(long long i=po[x].head;i;i=r[i].next)
	{
		if(vis2[r[i].to]) continue;
		po[r[i].to].top=new_id+1;
		po[r[i].to].father=me;
		dfs2(r[i].to);
	}
}
long long t[NUM];
void build(long long p,long long l,long long r)
{
	if(l==r)
	{
		t[p]=pn[l].w;
		return ;
	}
	long long mid=(r-l)/2+l;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	t[p]=max(t[p<<1],t[p<<1|1]);
	return ;
}
long long query(long long p,long long l,long long r,long long nl,long long nr,long long k)
{
	if(nl<=l&&r<=nr)
	{
		if(t[p]<k) return t[p];
		return 0;
	}
	long long mid=(r-l)/2+l,ans=0;
	if(nl<=mid)
	{
		long long q=query(p<<1,l,mid,nl,nr,k);//找不大于当前选取边(k)的最大边
		if(q<k) ans=max(ans,q);
	}
	if(nr>mid)
	{
		long long q=query(p<<1|1,mid+1,r,nl,nr,k);
		if(q<k) ans=max(ans,q);
	}
	t[p]=max(t[p<<1],t[p<<1|1]);
	return ans;
}
long long Query_Range(long long l,long long r,long long k)
{
	long long ans=0;
	l=po[l].id;
	r=po[r].id;
	while(pn[l].top!=pn[r].top)
	{
		if(pn[pn[l].top].depth>pn[pn[r].top].depth) swap(l,r);
		long long q=query(1,1,N,pn[r].top,r,k);
		if(q<k) ans=max(ans,q);
		r=pn[pn[r].top].father;
	}
	if(l>r) swap(l,r);
	long long q=query(1,1,N,l,r,k);
	if(q<k) ans=max(ans,q);
	return ans;
}
signed main()
{
	cin>>N>>M;
	//Kruskal求最小生成树
	for(long long i=1;i<=N;i++) fa[i]=i;
	long long cnt=0;
	for(long long i=1;i<=M;i++)
	{
		long long f,t,w;
		cin>>f>>t>>w;
		if(f>t) swap(f,t);
		if(f==t) continue;
		l[++cnt].f=f;
		l[cnt].t=t;
		l[cnt].w=w;
	}
	sort(l+1,l+1+cnt,cmp);
	for(long long i=1;i<=cnt;i++)
	{
		if(getfa(l[i].t)!=getfa(l[i].f))
		{
			ans_min+=l[i].w;
			fa[getfa(l[i].t)]=getfa(l[i].f);
			add(l[i].f,l[i].t,l[i].w);
			add(l[i].t,l[i].f,l[i].w);
			continue;
		}
		q.push(l[i]);
	}
	//ans_min为最小生成树的边权和
	//树链剖分
	dfs1(1);
	po[1].top=1;
	dfs2(1);
	build(1,1,N);
	//
	long long minn=LONG_LONG_MAX; 
	while(!q.empty())//找不在最小生成树中的次小边
	{
		line ll=q.front();
		q.pop();
		long long k=ll.w-Query_Range(ll.f,ll.t,ll.w);
		minn=min(minn,k!=0?k:minn);
	}
	cout<<ans_min+minn;
	return 0;
}