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.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Main {
    @SuppressWarnings("unchecked")
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();

        Object[] list = new Object[V];
        for (int i = 0; i < V; i++) {
            list[i] = new LinkedList<Edge>();
        }
        for (int i = 0; i < E; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            int w = sc.nextInt();
            LinkedList<Edge> edges = (LinkedList<Edge>)list[s];
            edges.add(new Edge(s, t, w));
            edges = (LinkedList<Edge>)list[t];
            edges.add(new Edge(t, s, w));
        }
        solve(V, E, list);
    }
     
    @SuppressWarnings("unchecked")
	public static void solve(int V, int E, Object[] list) {
        boolean[] visited = new boolean[V];
        PriorityQueue<Edge> que = new PriorityQueue<Edge>(10000, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.w - o2.w;
            }
        });
        
        int node = 0; // start
        visited[node] = true;
        int d = 0;
        int count = 0;
        
        LinkedList<Edge> edges = (LinkedList<Edge>)list[node];
        Iterator<Edge> it = edges.iterator();
        while(it.hasNext()) {
        	que.add(it.next());
        }
        while(que.isEmpty() == false) {
            Edge edge = que.poll();
            if (visited[edge.t])
                continue;
            
            visited[edge.t] = true;
            node = edge.t;
            d += edge.w;

            it = ((LinkedList<Edge>)list[node]).iterator(); 
            while(it.hasNext()) {
            	edge = it.next();
            	if (visited[edge.t])
            		continue;
            	que.add(edge);
            }
            
            count++;
            if (count >= V-1)
                break;
        }
        System.out.println(d);
    }
}
 
class Edge {
    int s;
    int t;
    int w;
    public Edge(int s, int t, int w) {
        this.s = s;
        this.t = t;
        this.w = w;
    }
}