import java.util.* ; import java.io.*; public class Solution { public static int getMinimumCost(int cities, int roads, int[][] Connections) { /* Q23 graph playlist , we need to find MST using prims algo */ //making graph ArrayList<ArrayList<pair>> graph = new ArrayList<>(); for(int i = 0 ;i < cities ; i++) graph.add(new ArrayList<>()); for(int[] connections : Connections){ graph.get(connections[0]-1).add(new pair(connections[1]-1,connections[2])); graph.get(connections[1]-1).add(new pair(connections[0]-1,connections[2])); } //Prims to find MST PriorityQueue<pair> q = new PriorityQueue<>(); q.add(new pair(0 , 0)); int ans = 0 , count = 0; boolean visited[] = new boolean[cities]; 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)); } } count ++; } return count == cities ? ans : -1; } 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; } } }