大红大紫

#include<bits/stdc++.h>
using namespace std;
int n,m,size,cnt,sum,dis[5005],book[5005],h[5005],pos[5005],u[200005],v[200005],w[200005],first[5005],nxt[200005];
void change(int x,int y){
	swap(h[x],h[y]);
	swap(pos[h[x]],pos[h[y]]);
	return;
}
void siftdown(int i){
	int t=0;
	while(i*2<=size){
		if(dis[h[i]]>dis[h[i*2]]){
			t=i*2;
		}
		else{
			t=i;
		}
		if(i*2+1<=size){
			if(dis[h[t]]>dis[h[i*2+1]]){
				t=i*2+1;
			}
		}
		if(t!=i){
			change(t,i);
			i=t;
		}
		else{
			break;
		}
	}
	return;
}
void siftup(int i){
	bool flag=false;
	if(i==1){
		return;
	}
	while(i!=1&&flag==false){
		if(dis[h[i]]<dis[h[i/2]]){
			change(i,i/2);
		}
		else{
			flag=true;
		}
		i/=2;
	}
	return;
}
int pop(){
	int t=h[1];
	h[1]=h[size];
	pos[h[1]]=1;
	size--;
	siftdown(1);
	return t;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
	}
	for(int i=m+1;i<=2*m;i++){
		u[i]=v[i-m];
		v[i]=u[i-m];
		w[i]=w[i-m];
	}
	for(int i=1;i<=n;i++){
		first[i]=-1;
	}
	for(int i=1;i<=2*m;i++){
		nxt[i]=first[u[i]];
		first[u[i]]=i;
	}
	book[1]=true;
	cnt++;
	for(int i=2;i<=n;i++){
		dis[i]=1e9+5;
	}
	int k=first[1];
	while(k!=-1){
		dis[v[k]]=w[k];
		k=nxt[k];
	}
	size=n;
	for(int i=1;i<=size;i++){
		h[i]=i;
		pos[i]=i;
	}
	for(int i=size/2;i>=1;i--){
		siftdown(i);
	}
	pop();
	while(cnt<n){
		int j=pop();
		if(dis[j]==1e9+5){
			cout<<"orz"<<endl;
			return 0;
		}
		book[j]=1;
		cnt++;
		sum=sum+dis[j];
		k=first[j];
		while(k!=-1){
			if(book[v[k]]==0&&dis[v[k]]>w[k]){
				dis[v[k]]=w[k];
				siftup(pos[v[k]]);
			}
			k=nxt[k];
		}
	}
	cout<<sum<<endl;
	return 0;
}

%%%