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 JAVA):

Solution:
import java.util.*;
import java.lang.*;

class Main {
	int parents[];
	int rank[];

	public void run() {
		Scanner scanner = new Scanner(System.in);
		int numVertices = scanner.nextInt();
		int numEdges = scanner.nextInt();
		int src, dest, weight;

		// Build graph
		Graph G = new Graph(numVertices, numEdges);

		for(int i = 0; i < numEdges; i++) {
			src = scanner.nextInt();
			dest = scanner.nextInt();
			weight = scanner.nextInt();

			G.addEdge(i, src, dest, weight);
		}

		// Build disjoint sets
		parents = new int[numVertices];
		rank = new int[numVertices];

		for(int i = 0; i < numVertices; i++) {
			createSet(i);
		}

		// Run Kruskal algorithm and print sum of weights of the MST
		System.out.println(KruskalMST(G, numVertices, numEdges));
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public void createSet(int n) {
		parents[n] = n;
		rank[n] = 0;
	}

	public int findSet(int n) {
		if(n != parents[n])
			parents[n] = findSet(parents[n]);
		return parents[n];
	}

	public void union(int x, int y) {
		int xroot = findSet(x);
		int yroot = findSet(y);

		if(xroot == yroot)
			return;

		if(rank[xroot] > rank[yroot]) {
			parents[yroot] = xroot;
		} else {
			parents[xroot] = yroot;
			if(rank[xroot] == rank[yroot])
				rank[yroot]++;
		}
	}

	public int KruskalMST(Graph G, int numVertices, int numEdges) {
		Edge result[] = new Edge[numVertices];
		Edge edges[] = G.getEdges();

		// Sort all edges of graph G
		Arrays.sort(edges);

		int sum = 0;
		int i = 0, e = 0;
		while(e < numVertices-1) {
			
			// get the next edge with minimum weight
			Edge nextEdge = edges[i++];

			int x = findSet(nextEdge.getSrc());
			int y = findSet(nextEdge.getDest());

			if(x != y) { // if including this edge doesn't form a cycle
				result[e++] = nextEdge;
				sum += nextEdge.getWeight();
				union(x, y);
			}
		}

		return sum;
	}

	class Graph {
		private int V, E;
		private Edge edges[];

		public Graph(int v, int e) {
			V = v;
			E = e;
			edges = new Edge[e];
		}

		public void addEdge(int i, int src, int dest, int weight) {
			if(i >= E) 
				return;

			edges[i] = new Edge(src, dest, weight);
		}

		public Edge[] getEdges() {
			return edges;
		}
	}

	class Edge implements Comparable<Edge>{
		private int src, dest, weight;

		public Edge(int s, int d, int w) {
			src = s;
			dest = d;
			weight = w;
		}

		public int compareTo(Edge anotherEdge) {
			return this.weight - anotherEdge.weight;
		}

		public int getSrc() {
			return src;
		}

		public int getDest() {
			return dest;
		}

		public int getWeight() {
			return weight;
		}
	}
}