原贴，代码改了一点，看起来不方便

悬赏6yuan，严格次小生成树代码求调，wa4，tle5，ac3

#include<stdio.h>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#define mp(ck1,ck2,ck3) make_pair(ck1,make_pair(ck2,ck3))
#define mk(ck1,ck2) make_pair(ck1,ck2)
using namespace std;
map<pair<int,int>,int>s;
pair<int,pair<int,int> >p[100005][25];
bool dis[5007],rode[400007];
int to[400007],v[400007],nex[400007],fir[5007],d[100005],from[400007];
int a,b,c,n,m,k=0,ans=0,sum=10000077;
struct node{ int l,r,fa; }nt[100007];
priority_queue<pair<int,pair<int,int> > >q;
void add(int x,int y,int z){
	to[++k]=y;
	v[k]=z;
	from[k]=x;
	nex[k]=fir[x];
	fir[x]=k;
}
int lca(int a,int b,int c){
	//cout<<"PO"<<a<<" "<<b<<"PO";
	if(d[a]>d[b])swap(a,b);
	int mama=0,mami=0,anser=0;
	for(int i=20;i>=0;i--)
		if(d[a]<=d[b]-(1<<i)){
			set<int>q;
        	q.insert(p[b][i].second.first);
			q.insert(p[b][i].second.second);
			q.insert(mama);
			q.insert(mami);
			auto it=q.end();
			mama=*(--it);
			mami=*(--it);
	//cout<<mama<<" "<<mami<<"               ";
			b=p[b][i].first;
		}
	//cout<<mama<<" "<<mami<<"               ";
	if(a==b){
		//cout<<"!";
		anser=c-mama;
		if(anser==0)anser=c-mami;
		return anser;
	}
	for(int i=20;i>=0;i--)
		if(p[a][i]==p[b][i])continue;
        //else a=p[a][i],b=p[b][i];  
        else{
        	set<int>q;
        	q.insert(p[a][i].second.first);
			q.insert(p[a][i].second.second);
        	q.insert(p[b][i].second.first);
			q.insert(p[b][i].second.second);
			q.insert(mama);
			q.insert(mami);
	//cout<<mama<<" "<<mami<<"               ";
			auto it=q.end();
			mama=*(--it);
			mami=*(--it);
//	cout<<mama<<" "<<mami<<"               "<<endl;
			a=p[a][i].first;
			b=p[b][i].first;
        }
        set<int>pq;
        pq.insert(p[a][0].second.first);
		pq.insert(p[a][0].second.second);
        pq.insert(p[b][0].second.first);
		pq.insert(p[b][0].second.second);
		pq.insert(mama);
		pq.insert(mami);
		auto it=pq.end();
		mama=*(--it);
		mami=*(--it);
        //cout<<"{}"<<c<<"{}";
	anser=c-mama;
	if(anser==0)anser=c-mami;
	//cout<<mama<<" "<<mami<<"            ";
	return anser;
}
void build(int u,int faa){
	d[u]=d[faa]+1;
	nt[u].fa=faa;
	p[u][0].first=faa;
	p[u][0].second.first=s[mk(u,faa)];
	//cout<<"p[u][0]:"<<u<<" "<<p[u][0].second.first<<endl;
	for(int i=1;(1<<i)<=d[u]-1;i++){
		p[u][i].first=p[p[u][i-1].first][i-1].first;
		//p[u][i].second.first=max(p[p[u][i-1].first][i-1].second.first,p[u][i-1].second.first);
		set<int>q;
		q.insert(p[u][i-1].second.first);
		q.insert(p[u][i-1].second.second);
		q.insert(p[p[u][i-1].first][i-1].second.first);
		q.insert(p[p[u][i-1].first][i-1].second.second);
		//cout<<"abcdefg"<<u<<" "<<i<<" ";
		//for(auto it=q.begin();it!=q.end();it++)cout<<*it<<" ";cout<<endl;
		auto it=q.end();
		p[u][i].second.second=*(--it);
		p[u][i].second.first=*(--it);
	}
	for(int i=fir[u],j=1;i;i=nex[i]){
		if(rode[i]){
			if(j==1)nt[u].l=to[i],j++;
			else nt[u].r=to[i];
			build(to[i],u);
		}
	}
}
int main(){
	cin>>n>>m;
	while(m--){
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
		if(s[mk(a,b)]!=0)s[mk(a,b)]=min(s[mk(a,b)],c),s[mk(b,a)]=min(s[mk(b,a)],c);
		else s[mk(a,b)]=c,s[mk(b,a)]=c;
	}
	q.push(mp(0,1,0));
	while(!q.empty()){
		a=q.top().second.first; 
		b=q.top().first;
		c=q.top().second.second;
		q.pop();
		if(dis[a])continue;
		rode[c]=1;
		dis[a]=1;
		ans+=-b;
		for(int i=fir[a];i;i=nex[i]){
			if(dis[to[i]])continue;
			q.push(mp(-v[i],to[i],i));
		}
	}
	d[1]=0;
	//cout<<ans;
	build(1,0);
	for(int i=1;i<=k;i++){
		if(rode[k])continue;
		else{
			//sum=min(sum,v[i]-lca(x,y));
			if(lca(from[i],to[i],v[i])>0)
			sum=min(sum,lca(from[i],to[i],v[i]));
		}
	}
	cout<<ans+sum;
	return 0;
}