#include
#include <string.h>
#include
#include
#include
#include
#include <string>
#include
#include
#include <set>
#include
#include
#define LL long long int
#define N 100000+10 //最大节点数
#define M 1000000+10 //最大的边数
#define MOD 142857
//N<=10^5, M<=10^6
using namespace std;
int n, m;
struct node
{
int v, w;
bool operator<(const node &dd)const{
return w>dd.w;
} //权值小的优先
};
vectorq[N];
bool vis[N];
//堆优化的prim算法
LL ans;
void queue_prim()
{
//以节点1为起点进行扩展安全边 生成最小树
priority_queueque;
while(!que.empty())
que.pop(); //初始化清空优先队列 维护一个小根堆
//这样每次找安全边的速度就提高了
ans = 0;
memset(vis, false, sizeof(vis));
for(int i=0; i1].size(); i++){
que.push(q[1][i]); //将起点的所有连接边全部加入队列中来
}
vis[1]=true;
int edge=n-1;//边数
node cur;
while(edge--)
{
cur = que.top();
que.pop();//这个地方需要注意一下
//并不是每个从优先队列取出来的边都是可以加到生成树上去的
if(vis[cur.v]==true){
while(vis[cur.v]){
cur=que.top(); que.pop();
}
}
ans = ans+cur.w; //printf("%d-- ", cur.w );
vis[cur.v]=true; //加入生成树的该点将被标记访问
for(int i=0; i){
if(vis[ q[cur.v][i].v ]==false) //当前加入生成树的点可以扩充出的边指向的节点
que.push(q[cur.v][i]);//如果没有被访问才会加入到队列当中来
}
}
}
int main()
{
scanf("%d %d", &n, &m);
int i, j;
int u, v, w;
node cur;
for(i=0; i<=n; i++)
q[i].clear();
for(i=0; i)
{
scanf("%d %d %d", &u, &v, &w);
cur.v=v; cur.w=w;
q[u].push_back(cur);
cur.v=u;
q[v].push_back(cur); //建立双向边
}
queue_prim();
printf("%lld\n", ans );
return 0;
}