树剖 TLE on #12

#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
inline LL read(){
	LL res=0,fl=1;
	char ch=getchar();
	while(!(ch>='0' && ch<='9')){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0' && ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
	return res*fl;
}
inline LL max(LL a,LL b){return a>b?a:b;}
inline LL min(LL a,LL b){return a<b?a:b;}
inline void swap(int &a,int &b){int c;c=a;a=b;b=c;}
const int MAXN=1e6+5;
int n,m,tot=0,p[MAXN];
LL ans=ans=1e18;
int si[MAXN],dep[MAXN],fa[MAXN],son[MAXN],wson[MAXN],id[MAXN],top[MAXN],sp[MAXN];
bool tri[MAXN];
struct Edge{
	int v,w,id;
};
vector<Edge> e[MAXN];
struct wEdge{
	int x,y,w,id;
}a[MAXN];
struct Segment_Tree{
	int l,r,maxv,smax;
	#define ls (k<<1)
	#define rs (k<<1|1)
	#define l(k) tr[k].l
	#define r(k) tr[k].r
	#define maxv(k) tr[k].maxv
	#define smax(k) tr[k].smax
	#define mid(k) ((tr[k].l+tr[k].r)>>1)
}tr[MAXN<<2];

inline pair<int,int> merge(int a,int b,int c,int d){
	int t[4]={a,b,c,d};
	sort(t,t+4);
	int maxv=t[3],smax=-1;
	for(int i=2;i>=0;i--)if(t[i]!=t[i+1]){smax=t[i];break;}
	return make_pair(maxv,smax);
}

inline void pushup(int k){
	pair<int,int> p=merge(maxv(ls),smax(ls),maxv(rs),smax(rs));
	maxv(k)=p.first,smax(k)=p.second;
}

inline void build(int k,int l,int r){
	l(k)=l,r(k)=r;
	if(l==r){
		maxv(k)=sp[l];
		smax(k)=-1;
		return;
	}
	build(ls,l,mid(k));
	build(rs,mid(k)+1,r);
	pushup(k);
}

inline pair<int,int> query(int k,int l,int r){
	if(l(k)>=l && r(k)<=r) return make_pair(maxv(k),smax(k));
	pair<int,int> lres,rres;
	if(l<=mid(k) && r<=mid(k))return query(ls,l,r);
	if(l>mid(k) && r>mid(k))return query(rs,l,r);
	lres=query(ls,l,r),rres=query(rs,l,r);
	return merge(lres.first,lres.second,rres.first,rres.second);
}

inline bool cmp(wEdge a,wEdge b){
	return a.w<b.w;
}

inline int find(int x){
	if(p[x]==x)return x;
	return p[x]=find(p[x]);
}

inline void dfs_son(int x,int f,int d){
	si[x]=1;
	dep[x]=d;
	fa[x]=f;
	int maxson=0;
	for(int i=0;i<e[x].size();i++){
		int y=e[x][i].v,w=e[x][i].w,eid=e[x][i].id;
		if(!tri[eid])continue;
		if(y!=f){
			dfs_son(y,x,d+1);
			if(si[y]>maxson)maxson=si[y],son[x]=y,wson[x]=w;
		}
	}
}

inline void dfs_chain(int x,int topf,int z){
	id[x]=++tot;
	sp[tot]=z;
	top[x]=topf;
	if(!son[x])return;
	dfs_chain(son[x],topf,wson[x]);
	for(int i=0;i<e[x].size();i++){
		int y=e[x][i].v,w=e[x][i].w,eid=e[x][i].id;
		if(!tri[eid])continue;
		if(y!=fa[x] && y!=son[x])dfs_chain(y,y,w);
	}
}

inline int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}

inline int findson(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		if(fa[top[x]]==y)return top[x];
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return son[x];
}

inline pair<int,int> range_query(int x,int y){
	pair<int,int> res=make_pair(-1,-1),tmp;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		tmp=query(1,id[top[x]],id[x]);
		res=merge(res.first,res.second,tmp.first,tmp.second);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);	
	tmp=query(1,id[x],id[y]);
	res=merge(res.first,res.second,tmp.first,tmp.second);
	return res;
}

signed main() {
	memset(tri,0,sizeof tri);
	int x,y,w,px,py,eid,minw=0;
	n=read(),m=read();
	for(int i=1;i<=n;i++)p[i]=i;
	for(int i=1;i<=m;i++){
		x=read(),y=read(),w=read();
		e[x].push_back({y,w,i});
		e[y].push_back({x,w,i});
		a[i]={x,y,w,i};
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++){
		x=a[i].x,y=a[i].y,w=a[i].w,eid=a[i].id;
		px=find(x),py=find(y);
		if(px!=py){
			p[px]=py;
			tri[eid]=1;
			minw+=w;
		}
	}
	dfs_son(1,1,1);
	dfs_chain(1,1,0);
	build(1,1,n);
	int rt,sonx,sony;
	for(int i=1;i<=m;i++){
		x=a[i].x,y=a[i].y,w=a[i].w,eid=a[i].id;
		if(tri[eid] || x==y)continue;
		rt=lca(x,y);
		if(rt)sonx=findson(x,rt),sony=findson(y,rt);
		pair<int,int> p,l,r;
		if(sonx)l=range_query(x,sonx);
		if(sony)r=range_query(y,sony);
		p=merge(l.first,l.second,r.first,r.second);
		int secw=p.first==w?p.second:p.first,smin=minw+w-secw;
		if(secw==-1)continue;
		ans=min(ans,smin);
	}
	cout<<ans<<'\n';
	return 0;
}