#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> pii;

const int maxn=5e5+10;
const int inf=1e9+7;
int n,m,ans,sum,cnt,dis[maxn],vis[maxn];
struct node {
	int v;
	ll dis;
};
vector<node> g[maxn];

inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}

inline void write(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

inline void prim(int x) {
	priority_queue <pii,vector<pii>,greater<pii> >pq;
	memset(dis,0x7f7f7f,sizeof dis);
	dis[x]=0;
	pq.push(make_pair(x,0));
	while(!pq.empty()&&cnt<n) {
		int u=pq.top().first,d=pq.top().second;
		pq.pop();
		if(vis[u]) continue;
		cnt++;
		sum+=d;
		vis[u]=1;
		for(int i=0; i<g[u].size(); ++i) {
			int v=g[u][i].v,w=g[u][i].dis;
			if(dis[v]>w) dis[v]=w,pq.push(make_pair(v,dis[v]));
		}
	}
}

signed main() {
//	freopen("prim.in","r",stdin);
//	freopen("prim.out","w",stdout);
	n=read(),m=read();
	for(int i=1; i<=m; ++i) {
		int u=read(),v=read(),w=read();
		g[u].push_back(node {v,w});
		g[v].push_back(node {u,w});
	}
	prim(1);
	if(cnt==n) write(sum),puts("");
	else puts("orz");
	return 0;
}

模板↑

数据：

样例：

5 18
2 4 276
3 3 435
3 4 608
2 4 860
1 2 318
1 3 547
5 4 419
2 5 98
1 5 460
5 3 399
3 5 240
3 2 733
3 3 903
4 2 909
5 2 206
3 4 810
2 1 115
2 3 419

答案输出：729

代码输出：908