Problem: Find the sum of weights of edges of the Minimum Spanning Tree for a given weighted undirected graph G = (V, E).

Constraints

* 1 ≤ |V| ≤ 10,000
* 0 ≤ |E| ≤ 100,000
* 0 ≤ wi ≤ 10,000
* The graph is connected
* There are no parallel edges
* There are no self-loops

Input


|V| |E|
s0 t0 w0
s1 t1 w1
:
s|E|-1 t|E|-1 w|E|-1


, where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target verticess of i-th edge (undirected) and wi represents the weight of the i-th edge.

Output

Print the sum of the weights of the Minimum Spanning Tree.

Examples

Input

4 6
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5


Output

3


Input

6 9
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6


Output

5

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

struct Edge{
  int to,cost;
  bool operator<(const Edge&a)const{
    return cost>a.cost;
  }
};
struct Graph{
  Graph(int n):E(n),T(n),N(n){}
  vector<vector<Edge>>E,T;
  int N;
  void add_edge(int a,int b,int c){
    E[a].push_back({b,c});
    E[b].push_back({a,c});
  }
  void prim(int s){
    bool visited[N];
    priority_queue<pair<Edge,int>>Q;
    memset(visited,0,N);
    Q.push({{s,0},-1});
    while(Q.size()){
      Edge e=Q.top().first;
      int from=Q.top().second;Q.pop();
      if(visited[e.to])continue;
      visited[e.to]=1;
      if(from+1)T[from].push_back(e),T[e.to].push_back({from,e.cost});
      for(auto&a:E[e.to])
      if(!visited[a.to])Q.push({a,e.to});
    }
  }
  int get_cost(){
    int ret=0;
    for(auto&a:T)for(auto&b:a)ret+=b.cost;
    return ret/2;
  }
  vector<Edge>* get_MST(){
    return T.data();
  }
};

int main(){
  int V,E,a,b,c;
  cin>>V>>E;
  Graph G(V);
  for(int i=0;i++<E;G.add_edge(a,b,c))cin>>a>>b>>c;
  G.prim(0);
  cout<<G.get_cost()<<endl;
}