Q20 Minimum Spanning Tree | Practice | GeeksforGeeks(prims algo)

//{ Driver Code Starts


import java.util.*;
import java.io.*;
import java.lang.*;

public class Main{
	static BufferedReader br;
	static PrintWriter ot;
    public static void main(String args[]) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		ot = new PrintWriter(System.out);
		int t = Integer.parseInt(br.readLine().trim());
		while(t-- > 0){
			String s[] = br.readLine().trim().split(" ");
			int V = Integer.parseInt(s[0]);
			int E = Integer.parseInt(s[1]);
			int edges[][] = new int[E][3];
			for(int i = 0; i < E; i++){
				s = br.readLine().trim().split(" ");
				edges[i][0] = Integer.parseInt(s[0]);
				edges[i][1] = Integer.parseInt(s[1]);
				edges[i][2] = Integer.parseInt(s[2]);
			}
			ot.println(new Solution().spanningTree(V, E, edges));
		}
		ot.close();
	}
}
// } Driver Code Ends


// User function Template for Java

class Solution{
	static int spanningTree(int V, int E, int edges[][]){
	    
	    ArrayList<ArrayList<pair>> graph = new ArrayList<>();
	    
	    for(int i = 0 ;i < V ; i++)
	    graph.add(new ArrayList<>());
	    
	    for(int[] edge : edges){
	        graph.get(edge[0]).add(new pair(edge[1],edge[2]));
	        graph.get(edge[1]).add(new pair(edge[0],edge[2]));
	    }
	    
	    PriorityQueue<pair> q = new PriorityQueue<>();
	    q.add(new pair(0 , 0));
	    
	    int ans = 0;
	    boolean visited[] = new boolean[V];
	    while(q.size() > 0){
	        pair rem = q.poll();
	        
	        int v = rem.v ,wt = rem.wt;
	        if(visited[v] == true)
	        continue;
	        
	        visited[v] = true;
	       // System.out.print(v + " " + wt + "\n");
	        ans += wt;
	
	        for(pair edge : graph.get(v)){
	            if(visited[edge.v] == false){
	                q.add(new pair(edge.v , edge.wt));
	            }
	        }
	        
	    }
	    
	    return ans;
	}
	
	public static class pair implements Comparable<pair>{
	    int v , wt ;
	    
	    pair(int v , int wt){
	        this. v = v;
	        this.wt = wt;
	    }
	    
	    public int compareTo(pair o){
	        return this.wt - o.wt;
	    }
	}
}