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;
typedef long long ll;
const ll MAX_V = 10000;
const ll MAX_E = 100000;
struct edge{
  ll u,v,cost;
  bool operator<(const edge &o) const {return cost < o.cost;}
  bool operator>(const edge &o) const {return cost > o.cost;}
};
ll V,E,Par[MAX_V],Rank[MAX_V] = {};edge G[MAX_E];
void init(ll n){
  for(ll i=0;i<n;i++) Par[i] = i;
}
ll find(ll x){
  if(x == Par[x]) return x;
  else return Par[x] = find(Par[x]);
}
void unite(ll x,ll y){
  x = find(x);y = find(y);
  if(x == y) return;
  if(Rank[x] < Rank[y]) swap(x,y);
  Par[y] = x;
  if(Rank[x] == Rank[y]) Rank[x]++;
}
bool same(ll x,ll y){
  return find(x) == find(y);
}
ll Kruskal(){
  sort(G,G+E);ll ans = 0,i;edge e;
  init(V);
  for(i=0;i<E;i++){
    e = G[i];
    if(!same(e.u,e.v)){
      ans += e.cost;
      unite(e.u,e.v);
    }
  }
  return ans;
}
int main(){
  ll i;scanf("%lld%lld",&V,&E);
  for(i=0;i<E;i++) scanf("%lld%lld%lld",&G[i].u,&G[i].v,&G[i].cost);
  printf("%lld\n",Kruskal());
}