RT，Prim 理论时间 $n^2+m$ 过了。

萌新刚学 Prim 来三倍经验然后过了。

不知道是不是堆优化导致过了。

最劣时间 345ms。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define double long double
//#define map unordered_map
//#pragma GCC optimize(2,3,"Ofast","inline")
const int N=1e5+10,M=1010,P=1e9+7,MOD=998244353;
const double PI=3.1415926,EPS=0.00001;
int n,m,U,V,W,su,dep[N],tot,ans;
bool vis[N];
vector<pair<int,int> >e[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>U>>V>>W;
		e[U].push_back(make_pair(V,W));
		e[V].push_back(make_pair(U,W));
	}
	memset(dep,0x3f,sizeof(dep));
	q.push(make_pair(0,1));dep[1]=0;
	while(q.size()){
		pair<int,int>f=q.top();q.pop();
		if(vis[f.second])continue;
		tot++;ans+=dep[f.second];
		vis[f.second]=1;
		for(auto v:e[f.second])if(v.second<dep[v.first]){
			dep[v.first]=v.second;
			q.push(make_pair(dep[v.first],v.first));
		}
	}
	if(tot!=n)cout<<"orz";
	else cout<<ans;
    return 0;
}
//note: