stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

using namespace std;



#define MAX_V 10000

#define INF 1e9

typedef pair<int, int> pii;



struct edge{

    int to, cost;

};



int V;

bool used[MAX_V];

vector<edge> G[MAX_V];



/*

  O(E log V)

  ?????°??±?????????????????´???vector?????????????????¨???

*/

int prim()

{

    priority_queue<pii, vector<pii>, greater<pii> > Q;

    Q.push(pii(0, 0));

    memset(used, false, sizeof(used));

    int res = 0;

  

    while (!Q.empty()) {

	pii p = Q.top(); Q.pop();

	int v = p.second;

	if (used[v]) continue;

	used[v] = true;

	res += p.first;

	for (int i = 0; i < (int)G[v].size(); i++) {

	    edge e = G[v][i];

	    Q.push(pii(e.cost, e.to));

	}

    }

    return res;

}



int main()

{

    int E,s,t,w;

    cin >> V >> E;

    for (int i = 0; i < E; i++) {

	cin >> s >> t >> w;

	G[s].push_back((edge){t, w});

	G[t].push_back((edge){s, w});

    }

    cout << prim() << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2679849481827237x):
#include<bits/stdc++.h>

using namespace std;



#define MAX 100000

#define MAX_E 100000



int par[MAX], rank_[MAX];



void init(int N)

{

    for (int i = 0; i < N; i++) {

	par[i] = i;

	rank_[i] = 0;

    }

}



int find(int x)

{

    if (par[x] == x) {

	return x;

    }

    return par[x] = find(par[x]);

}



void unite(int x, int y)

{

    x = find(x);

    y = find(y);



    if (x == y) return;



    if (rank_[x] < rank_[y]) {

	par[x] = y;

    } else {

	par[y] = x;

	if (rank_[x] == rank_[y]) {

	    rank_[x]++;

	}

    }

}



bool same(int x,int y)

{

    return (find(x) == find(y));

}



struct edge{ int u, v, cost; };



bool comp(const edge &e1, const edge &e2)

{

    return e1.cost < e2.cost;

}



int V,E;

edge es[MAX_E];



int kruskal()

{

    sort(es, es+E, comp);

    init(V); // init union_find

    int res = 0;

    for (int i = 0; i < E; i++) {

	edge e = es[i];

	if (!same(e.u, e.v)) {

	    unite(e.u, e.v);

	    res += e.cost;

	}

    }

    return res;

}



int main()

{

    int s,t,w;

    cin >> V >> E;

    for (int i = 0; i < E; i++) {

	cin >> s >> t >> w;

        es[i]=(edge){s, t, w};

    }

    cout << kruskal() << endl;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

using namespace std;



#define MAX_V 10000

#define INF 1e9

typedef pair<int, int> pii;



struct edge{

    int to, cost;

};



int V;

bool used[MAX_V];

vector<edge> G[MAX_V];



/*

  O(E log V)

  ?????°??±?????????????????´???vector?????????????????¨???

*/

int prim()

{

    priority_queue<pii, vector<pii>, greater<pii> > Q;

    Q.push(pii(0, 0));

    memset(used, false, sizeof(used));

    int res = 0;

  

    while (!Q.empty()) {

	pii p = Q.top(); Q.pop();

	int v = p.second;

	if (used[v]) continue;

	used[v] = true;

	res += p.first;

	for (int i = 0; i < (int)G[v].size(); i++) {

	    edge e = G[v][i];

	    Q.push(pii(e.cost, e.to));

	}

    }

    return res;

}



int main()

{

    int E,s,t,w;

    cin >> V >> E;

    for (int i = 0; i < E; i++) {

	cin >> s >> t >> w;

	G[s].push_back((edge){t, w});

	G[t].push_back((edge){s, w});

    }

    cout << prim() << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2551279682965517x):
#include<bits/stdc++.h>

using namespace std;

struct UnionFind{

  vector<int> r,p;

  UnionFind(){}

  UnionFind(int size){init(size);}

  void init(int size){

    r.resize(size,0);

    p.resize(size,0);

    for(int i=0;i<size;i++) r[i]=1,p[i]=i;

  }

  int find(int x){

    return (x==p[x]?x:p[x]=find(p[x]));

  }

  bool same(int x,int y){

    return find(x)==find(y);

  }

  void unite(int x,int y){

    x=find(x);y=find(y);

    if(x==y) return;

    if(r[x]<r[y]) swap(x,y);

    r[x]+=r[y];

    p[y]=x;

  }

};

struct edge{

  int from,to,cost;

  edge(){}

  edge(int from,int to,int cost):from(from),to(to),cost(cost){}

  bool operator<(const edge& e) const{

    return cost<e.cost;

  }

};

int kruskal(int N,vector<edge> edges){

  int res=0;

  sort(edges.begin(),edges.end());

  UnionFind uf(N+1);

  for(int i=0;i<(int)edges.size();i++){

    edge e=edges[i];

    if(!uf.same(e.from,e.to)){

      res+=e.cost;

      uf.unite(e.from,e.to);

    }

  }

  return res;

}

int main(){

  int V,E;

  cin>>V>>E;

  vector<edge> edges(E);

  for(int i=0;i<E;i++)

    cin>>edges[i].from>>edges[i].to>>edges[i].cost;

  cout<<kruskal(V,edges)<<endl;

  return 0;

}



/*

verified on 2017/04/26

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

*/
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define MAX_V 11111

typedef pair<int,int> P;

vector<P> G[MAX_V];

bool used[MAX_V];

int prim(){

  int res=0;

  priority_queue<P,vector<P>,greater<P> > q;

  q.push(P(0,0));

  memset(used,0,sizeof(used));

  while(!q.empty()){

    P p=q.top();q.pop();

    int v=p.second,d=p.first;

    if(used[v]) continue;

    used[v]=1;

    res+=d;

    for(int i=0;i<(int)G[v].size();i++){

      q.push(G[v][i]);

    }

  }

  return res;

}

int main(){

  int V,E;

  cin>>V>>E;

  for(int i=0;i<E;i++){

    int s,t,u;

    cin>>s>>t>>u;

    G[s].push_back(P(u,t));

    G[t].push_back(P(u,s));

  }

  cout<<prim()<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2872641109364653x):
#include<bits/stdc++.h>

using namespace std;

struct UnionFind{

  vector<int> r,p;

  UnionFind(){}

  UnionFind(int size){init(size);}

  void init(int size){

    r.resize(size,0);

    p.resize(size,0);

    for(int i=0;i<size;i++) r[i]=1,p[i]=i;

  }

  int find(int x){

    return (x==p[x]?x:p[x]=find(p[x]));

  }

  bool same(int x,int y){

    return find(x)==find(y);

  }

  void unite(int x,int y){

    x=find(x);y=find(y);

    if(x==y) return;

    if(r[x]<r[y]) swap(x,y);

    r[x]+=r[y];

    p[y]=x;

  }

};

struct edge{

  int from,to,cost;

  edge(){}

  edge(int from,int to,int cost):from(from),to(to),cost(cost){}

  bool operator<(const edge& e) const{

    return cost<e.cost;

  }

};

int kruskal(int N,vector<edge> edges){

  int res=0;

  sort(edges.begin(),edges.end());

  UnionFind uf(N+1);

  for(int i=0;i<(int)edges.size();i++){

    edge e=edges[i];

    if(!uf.same(e.from,e.to)){

      res+=e.cost;

      uf.unite(e.from,e.to);

    }

  }

  return res;

}

int main(){

  int V,E;

  cin>>V>>E;

  vector<edge> edges(E);

  for(int i=0;i<E;i++)

    cin>>edges[i].from>>edges[i].to>>edges[i].cost;

  cout<<kruskal(V,edges)<<endl;

  return 0;

}



/*

verified on 2017/04/26

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

*/
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

using namespace std;



#define MAX_V 10000

#define INF 1e9

typedef pair<int, int> pii;



struct edge{

    int to, cost;

};



int V;

bool used[MAX_V];

vector<edge> G[MAX_V];



/*

  O(E log V)

  ?????°??±?????????????????´???vector?????????????????¨???

*/

int prim()

{

    priority_queue<pii, vector<pii>, greater<pii> > Q;

    Q.push(pii(0, 0));

    memset(used, false, sizeof(used));

    int res = 0;

  

    while (!Q.empty()) {

	pii p = Q.top(); Q.pop();

	int v = p.second;

	if (used[v]) continue;

	used[v] = true;

	res += p.first;

	for (int i = 0; i < (int)G[v].size(); i++) {

	    edge e = G[v][i];

	    Q.push(pii(e.cost, e.to));

	}

    }

    return res;

}



int main()

{

    int E,s,t,w;

    cin >> V >> E;

    for (int i = 0; i < E; i++) {

	cin >> s >> t >> w;

	G[s].push_back((edge){t, w});

	G[t].push_back((edge){s, w});

    }

    cout << prim() << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.254316523653713x):
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

//BEGIN CUT HERE

struct Kruskal{



  struct UnionFind{

    int n;

    vector<int> r,p;

    UnionFind(){}

    UnionFind(int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}

    int find(int x){

      return (x==p[x]?x:p[x]=find(p[x]));

    }

    bool same(int x,int y){

      return find(x)==find(y);

    }

    void unite(int x,int y){

      x=find(x);y=find(y);

      if(x==y) return;

      if(r[x]<r[y]) swap(x,y);

      r[x]+=r[y];

      p[y]=x;

    }

  };

  

  struct edge{

    int from,to,cost,used;

    edge(){}

    edge(int from,int to,int cost):

      from(from),to(to),cost(cost),used(0){}

    bool operator<(const edge& e) const{

      return cost<e.cost;

    }

  };



  int n;

  vector<edge> edges;



  Kruskal(){}

  Kruskal(int sz):n(sz){}

  

  void add_edge(int u,int v,int c){

    edges.emplace_back(u,v,c);

  }



  void input(int m,int offset=0){

    int a,b,c;

    for(int i=0;i<m;i++){

      cin>>a>>b>>c;

      add_edge(a+offset,b+offset,c);

    }

  }

  

  int build(){

    sort(edges.begin(),edges.end());

    UnionFind uf(n+1);

    int res=0;

    for(auto &e:edges){

      if(!uf.same(e.from,e.to)){

	res+=e.cost;

	uf.unite(e.from,e.to);

	e.used=1;

      }

    }

    return res;

  }

};

//END CUT HERE

int main(){

  int V,E;

  cin>>V>>E;

  Kruskal kruskal(V);

  kruskal.input(E);

  cout<<kruskal.build()<<endl;

  return 0;

}



/*

  verified on 2018/01/11

  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

*/
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define MAX_V 11111

typedef pair<int,int> P;

vector<P> G[MAX_V];

bool used[MAX_V];

int prim(){

  int res=0;

  priority_queue<P,vector<P>,greater<P> > q;

  q.push(P(0,0));

  memset(used,0,sizeof(used));

  while(!q.empty()){

    P p=q.top();q.pop();

    int v=p.second,d=p.first;

    if(used[v]) continue;

    used[v]=1;

    res+=d;

    for(int i=0;i<(int)G[v].size();i++){

      q.push(G[v][i]);

    }

  }

  return res;

}

int main(){

  int V,E;

  cin>>V>>E;

  for(int i=0;i<E;i++){

    int s,t,u;

    cin>>s>>t>>u;

    G[s].push_back(P(u,t));

    G[t].push_back(P(u,s));

  }

  cout<<prim()<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2864318901644627x):
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

//BEGIN CUT HERE

struct Kruskal{



  struct UnionFind{

    int n;

    vector<int> r,p;

    UnionFind(){}

    UnionFind(int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}

    int find(int x){

      return (x==p[x]?x:p[x]=find(p[x]));

    }

    bool same(int x,int y){

      return find(x)==find(y);

    }

    void unite(int x,int y){

      x=find(x);y=find(y);

      if(x==y) return;

      if(r[x]<r[y]) swap(x,y);

      r[x]+=r[y];

      p[y]=x;

    }

  };

  

  struct edge{

    int from,to,cost,used;

    edge(){}

    edge(int from,int to,int cost):

      from(from),to(to),cost(cost),used(0){}

    bool operator<(const edge& e) const{

      return cost<e.cost;

    }

  };



  int n;

  vector<edge> edges;



  Kruskal(){}

  Kruskal(int sz):n(sz){}

  

  void add_edge(int u,int v,int c){

    edges.emplace_back(u,v,c);

  }



  void input(int m,int offset=0){

    int a,b,c;

    for(int i=0;i<m;i++){

      cin>>a>>b>>c;

      add_edge(a+offset,b+offset,c);

    }

  }

  

  int build(){

    sort(edges.begin(),edges.end());

    UnionFind uf(n+1);

    int res=0;

    for(auto &e:edges){

      if(!uf.same(e.from,e.to)){

	res+=e.cost;

	uf.unite(e.from,e.to);

	e.used=1;

      }

    }

    return res;

  }

};

//END CUT HERE

int main(){

  int V,E;

  cin>>V>>E;

  Kruskal kruskal(V);

  kruskal.input(E);

  cout<<kruskal.build()<<endl;

  return 0;

}



/*

  verified on 2018/01/11

  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

*/
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

using namespace std;



#define MAX_V 10000

#define INF 1e9

typedef pair<int, int> pii;



struct edge{

    int to, cost;

};



int V;

bool used[MAX_V];

vector<edge> G[MAX_V];



/*

  O(E log V)

  ?????°??±?????????????????´???vector?????????????????¨???

*/

int prim()

{

    priority_queue<pii, vector<pii>, greater<pii> > Q;

    Q.push(pii(0, 0));

    memset(used, false, sizeof(used));

    int res = 0;

  

    while (!Q.empty()) {

	pii p = Q.top(); Q.pop();

	int v = p.second;

	if (used[v]) continue;

	used[v] = true;

	res += p.first;

	for (int i = 0; i < (int)G[v].size(); i++) {

	    edge e = G[v][i];

	    Q.push(pii(e.cost, e.to));

	}

    }

    return res;

}



int main()

{

    int E,s,t,w;

    cin >> V >> E;

    for (int i = 0; i < E; i++) {

	cin >> s >> t >> w;

	G[s].push_back((edge){t, w});

	G[t].push_back((edge){s, w});

    }

    cout << prim() << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2541006677496789x):
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

//BEGIN CUT HERE

template<typename T>

struct Kruskal{

  

  struct edge{

    int from,to;

    T cost;

    int used;

    edge(){}

    edge(int from,int to,T cost):

      from(from),to(to),cost(cost),used(0){}

    bool operator<(const edge& e) const{

      return cost<e.cost;

    }

  };



  int n;

  vector<int> p,r;

  vector<edge> edges;



  Kruskal(){}

  Kruskal(int n):n(n){}



  void init(int n){

    r.assign(n,1);

    p.resize(n);

    iota(p.begin(),p.end(),0);

  }

  

  int find(int x){

    return (x==p[x]?x:p[x]=find(p[x]));

  }



  bool same(int x,int y){

    return find(x)==find(y);

  }



  void unite(int x,int y){

    x=find(x);y=find(y);

    if(x==y) return;

    if(r[x]<r[y]) swap(x,y);

    r[x]+=r[y];

    p[y]=x;

  }



  void add_edge(int u,int v,T c){

    edges.emplace_back(u,v,c);

  }



  void input(int m,int offset=0){

    int a,b;

    T c;

    for(int i=0;i<m;i++){

      cin>>a>>b>>c;

      add_edge(a+offset,b+offset,c);

    }

  }

  

  T build(){

    sort(edges.begin(),edges.end());

    init(n);

    T res=0;

    for(auto &e:edges){

      if(!same(e.from,e.to)){

	res+=e.cost;

	unite(e.from,e.to);

	e.used=1;

      }

    }

    return res;

  }

};

//END CUT HERE

int main(){

  int V,E;

  cin>>V>>E;

  Kruskal<int> kruskal(V);

  kruskal.input(E);

  cout<<kruskal.build()<<endl;

  return 0;

}



/*

  verified on 2018/01/11

  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

*/
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define MAX_V 11111

typedef pair<int,int> P;

vector<P> G[MAX_V];

bool used[MAX_V];

int prim(){

  int res=0;

  priority_queue<P,vector<P>,greater<P> > q;

  q.push(P(0,0));

  memset(used,0,sizeof(used));

  while(!q.empty()){

    P p=q.top();q.pop();

    int v=p.second,d=p.first;

    if(used[v]) continue;

    used[v]=1;

    res+=d;

    for(int i=0;i<(int)G[v].size();i++){

      q.push(G[v][i]);

    }

  }

  return res;

}

int main(){

  int V,E;

  cin>>V>>E;

  for(int i=0;i<E;i++){

    int s,t,u;

    cin>>s>>t>>u;

    G[s].push_back(P(u,t));

    G[t].push_back(P(u,s));

  }

  cout<<prim()<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2862105075123225x):
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

//BEGIN CUT HERE

template<typename T>

struct Kruskal{

  

  struct edge{

    int from,to;

    T cost;

    int used;

    edge(){}

    edge(int from,int to,T cost):

      from(from),to(to),cost(cost),used(0){}

    bool operator<(const edge& e) const{

      return cost<e.cost;

    }

  };



  int n;

  vector<int> p,r;

  vector<edge> edges;



  Kruskal(){}

  Kruskal(int n):n(n){}



  void init(int n){

    r.assign(n,1);

    p.resize(n);

    iota(p.begin(),p.end(),0);

  }

  

  int find(int x){

    return (x==p[x]?x:p[x]=find(p[x]));

  }



  bool same(int x,int y){

    return find(x)==find(y);

  }



  void unite(int x,int y){

    x=find(x);y=find(y);

    if(x==y) return;

    if(r[x]<r[y]) swap(x,y);

    r[x]+=r[y];

    p[y]=x;

  }



  void add_edge(int u,int v,T c){

    edges.emplace_back(u,v,c);

  }



  void input(int m,int offset=0){

    int a,b;

    T c;

    for(int i=0;i<m;i++){

      cin>>a>>b>>c;

      add_edge(a+offset,b+offset,c);

    }

  }

  

  T build(){

    sort(edges.begin(),edges.end());

    init(n);

    T res=0;

    for(auto &e:edges){

      if(!same(e.from,e.to)){

	res+=e.cost;

	unite(e.from,e.to);

	e.used=1;

      }

    }

    return res;

  }

};

//END CUT HERE

int main(){

  int V,E;

  cin>>V>>E;

  Kruskal<int> kruskal(V);

  kruskal.input(E);

  cout<<kruskal.build()<<endl;

  return 0;

}



/*

  verified on 2018/01/11

  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

*/
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

using namespace std;



#define MAX_V 10000

#define INF 1e9

typedef pair<int, int> pii;



struct edge{

    int to, cost;

};



int V;

bool used[MAX_V];

vector<edge> G[MAX_V];



/*

  O(E log V)

  ?????°??±?????????????????´???vector?????????????????¨???

*/

int prim()

{

    priority_queue<pii, vector<pii>, greater<pii> > Q;

    Q.push(pii(0, 0));

    memset(used, false, sizeof(used));

    int res = 0;

  

    while (!Q.empty()) {

	pii p = Q.top(); Q.pop();

	int v = p.second;

	if (used[v]) continue;

	used[v] = true;

	res += p.first;

	for (int i = 0; i < (int)G[v].size(); i++) {

	    edge e = G[v][i];

	    Q.push(pii(e.cost, e.to));

	}

    }

    return res;

}



int main()

{

    int E,s,t,w;

    cin >> V >> E;

    for (int i = 0; i < E; i++) {

	cin >> s >> t >> w;

	G[s].push_back((edge){t, w});

	G[t].push_back((edge){s, w});

    }

    cout << prim() << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2666596415001787x):
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

//BEGIN CUT HERE

template<typename T>

struct Kruskal{

  

  struct edge{

    int from,to;

    T cost;

    int used;

    edge(){}

    edge(int from,int to,T cost):

      from(from),to(to),cost(cost),used(0){}

    bool operator<(const edge& e) const{

      return cost<e.cost;

    }

  };



  int n;

  vector<int> p,r;

  vector<edge> edges;



  Kruskal(){}

  Kruskal(int n):n(n){}



  void init(int n){

    r.assign(n,1);

    p.resize(n);

    iota(p.begin(),p.end(),0);

  }

  

  int find(int x){

    return (x==p[x]?x:p[x]=find(p[x]));

  }



  bool same(int x,int y){

    return find(x)==find(y);

  }



  void unite(int x,int y){

    x=find(x);y=find(y);

    if(x==y) return;

    if(r[x]<r[y]) swap(x,y);

    r[x]+=r[y];

    p[y]=x;

  }



  void add_edge(int u,int v,T c){

    edges.emplace_back(u,v,c);

  }

  

  T build(){

    sort(edges.begin(),edges.end());

    init(n);

    T res=0;

    for(auto &e:edges){

      if(!same(e.from,e.to)){

        res+=e.cost;

        unite(e.from,e.to);

        e.used=1;

      }

    }

    return res;

  }

};

//END CUT HERE

int main(){

  int V,E;

  scanf("%d %d",&V,&E);

  Kruskal<int> ksk(V);

  for(int i=0;i<E;i++){

    int a,b,c;

    scanf("%d %d %d",&a,&b,&c);

    ksk.add_edge(a,b,c);

  }

  cout<<ksk.build()<<endl;

  return 0;

}



/*

  verified on 2018/10/22

  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

*/
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define MAX_V 11111

typedef pair<int,int> P;

vector<P> G[MAX_V];

bool used[MAX_V];

int prim(){

  int res=0;

  priority_queue<P,vector<P>,greater<P> > q;

  q.push(P(0,0));

  memset(used,0,sizeof(used));

  while(!q.empty()){

    P p=q.top();q.pop();

    int v=p.second,d=p.first;

    if(used[v]) continue;

    used[v]=1;

    res+=d;

    for(int i=0;i<(int)G[v].size();i++){

      q.push(G[v][i]);

    }

  }

  return res;

}

int main(){

  int V,E;

  cin>>V>>E;

  for(int i=0;i<E;i++){

    int s,t,u;

    cin>>s>>t>>u;

    G[s].push_back(P(u,t));

    G[t].push_back(P(u,s));

  }

  cout<<prim()<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2990910396871833x):
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

//BEGIN CUT HERE

template<typename T>

struct Kruskal{

  

  struct edge{

    int from,to;

    T cost;

    int used;

    edge(){}

    edge(int from,int to,T cost):

      from(from),to(to),cost(cost),used(0){}

    bool operator<(const edge& e) const{

      return cost<e.cost;

    }

  };



  int n;

  vector<int> p,r;

  vector<edge> edges;



  Kruskal(){}

  Kruskal(int n):n(n){}



  void init(int n){

    r.assign(n,1);

    p.resize(n);

    iota(p.begin(),p.end(),0);

  }

  

  int find(int x){

    return (x==p[x]?x:p[x]=find(p[x]));

  }



  bool same(int x,int y){

    return find(x)==find(y);

  }



  void unite(int x,int y){

    x=find(x);y=find(y);

    if(x==y) return;

    if(r[x]<r[y]) swap(x,y);

    r[x]+=r[y];

    p[y]=x;

  }



  void add_edge(int u,int v,T c){

    edges.emplace_back(u,v,c);

  }

  

  T build(){

    sort(edges.begin(),edges.end());

    init(n);

    T res=0;

    for(auto &e:edges){

      if(!same(e.from,e.to)){

        res+=e.cost;

        unite(e.from,e.to);

        e.used=1;

      }

    }

    return res;

  }

};

//END CUT HERE

int main(){

  int V,E;

  scanf("%d %d",&V,&E);

  Kruskal<int> ksk(V);

  for(int i=0;i<E;i++){

    int a,b,c;

    scanf("%d %d %d",&a,&b,&c);

    ksk.add_edge(a,b,c);

  }

  cout<<ksk.build()<<endl;

  return 0;

}



/*

  verified on 2018/10/22

  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp

*/