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>
#define rep(i, n) for (int i=0; i<(n); i++)
#define ll long long
using namespace std;

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

struct UnionFind {
  vector<int> par;
  UnionFind(int n) : par(n, -1) { }
  int root(int x) {
    if (par[x]<0) return x;
    else return par[x]=root(par[x]);
  }
  bool issame(int x, int y) {
    return root(x) == root(y);
  }
  void merge(int x, int y) {
    x=root(x); y=root(y);
    if (x==y) return ;
    if (-par[x]<-par[y]) swap(x, y);
    par[x]+=par[y];
    par[y]=x;
  }
};

const int MAX_E=100000;

edge es[MAX_E+1];
int V,E;

bool comp(const edge& e1, const edge& e2) {
  return e1.cost<e2.cost;
}

int kruskal() {
  sort(es, es+E, comp);
  UnionFind uf(V);
  int res=0;
  for (int i=0; i<E; i++) {
    edge e=es[i];
    if (!uf.issame(e.u, e.v)) {
      uf.merge(e.u, e.v);
      res+=e.cost;
    }
  }
  return res;
}


int main() {
  cin>>V>>E;
  rep(i, E) {
    int s,t,cost;
    cin>>s>>t>>cost;
    es[i]={s,t,cost};
  }
  int res=kruskal();
  cout<<res<<endl;
}