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.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;


public class Main{

	static int[] unionFind;
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		String[] first = s.nextLine().split(" ");
		int V = Integer.parseInt(first[0]);
		int E = Integer.parseInt(first[1]);
		unionFind = new int[V];
		for(int i=0 ; i<unionFind.length ; i++)
			unionFind[i] = i;
		ArrayList<Edge> edgeList = new ArrayList<Edge>();
		for(int i=0 ; i<E ; i++) {
			String[] line = s.nextLine().split(" ");
			Edge edge = new Edge(Integer.parseInt(line[0]), Integer.parseInt(line[1]), Integer.parseInt(line[2]));
			edgeList.add(edge);
		}
		Collections.sort(edgeList, new Comparator<Edge>() {
			public int compare(Edge e1, Edge e2) {
				return e1.weight - e2.weight;
			}
		});
		int result = 0;
		for(Edge e : edgeList) {
			if(getParent(e.start) == getParent(e.end))
				continue;
			unionFind[getParent(e.start)] = getParent(e.end);
			result += e.weight;
		}
		System.out.println(result);
	}

	public static int getParent(int index) {
		if(unionFind[index] == index)
			return index;
		return getParent(unionFind[index]);
	}

	public static class Edge{
		int start;
		int end;
		int weight;

		Edge(int start, int end, int weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}
	}

}