1 #include<cstdio>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<queue>
6 #include<algorithm>
7 using namespace std;
8 const int maxn=100000;
9 const int maxm=5000000;
10
11 int tb,from[maxm],to[maxm],len[maxm],next[maxm],first[maxn],n,m,ans;
12 bool is_select[maxn];//表示某个点i是否被选中
13 int cnt;//表示剩余的点数量
14 //建图
15 void addedge(int a,int b,int c){
16 tb++;
17 from[tb]=a;to[tb]=b;len[tb]=c;
18 next[tb]=first[a];
19 first[a]=tb;
20 }
21
22 struct u{
23 int a,c;
24 };
25
26 struct cmp{
27 bool operator()(u a,u b){
28 return a.c>b.c;
29 }
30 };
31
32 priority_queue<u,vector<u>,cmp> hep;//优先队列
33
34 void geted(int v) //从v号点出发 寻找没有访问过的点的边 加入队列
35 {
36 is_select[v]=1;
37 int p=first[v];
38 while(p!=0)
39 {
40 if(is_select[to[p]]==0)
41 {
42 u neo={to[p],len[p]};
43 hep.push(neo);
44 }
45 p=next[p];
46 }
47 }
48
49 int main()
50 {
51 scanf("%d %d",&n,&m);
52
53 for(int i=1,a,b,c;i<=m;i++)
54 {
55 scanf("%d%d%d",&a,&b,&c);
56 addedge(a,b,c);
57 addedge(b,a,c);
58 }
59 cnt=n-1;
60 geted(1);
61 while(cnt>0 && !hep.empty()){
62 u hd=hep.top();
63 while(is_select[hd.a]){
64 hep.pop();
65 hd=hep.top();
66 }
67 hep.pop();
68 ans+=hd.c;
69 geted(hd.a);
70 cnt--;
71 }
72
73 printf("%d",ans);
74 return 0;
75 }
