Hi I need help writing a java program that implements Prim's algorithm. The imput of the program is given by the scanner with an undirected graph. First input line is the number of vertices, second input is the number of undirected edges. After that the input is a matrix of 3 by the number of undirected edges. The matrix firt 2 column contain the end points and the third column contains the weight . The output of the program is an integer representing the sum of all the edges that make up the minimum spanning tre. I have attach a picture for farther details. THANKS You are given an undirected graph.Calculate the minimum spanning tree.You will ouput only the total sum of all edges.All vertices are accessible from all other vertices in the graph. There are no isolatedvertices.Input FormatFirst line is number of vertices: vSecond line is number of (undirected) edges: eThe next e lines contain the 3 values: the two endpoints and the cost value of the edgethat joins them.ConstraintsThe number of vertices will be less than 16edge cost values will be less than 100Output FormatOutput a single integer, the sum of all edges that make up the minimum spanning tree.Sample Input 0460 190 290 3 101 2 21 3 10239Sample Output 020Explanation 0The graph contains 4 vertices and 6 undirected edges.The sum of the edges in the MST is 20:v1v2: 9v2 - v3: 2v3 v4: 99 +2+ 9 = 20

Answer: We have done code in Java programming language and we have also attached the code scrernshot and output JAVA CODE import java.util.*;public class Main{ public void mst(int Graph[][], int V) { int INF = 9999999; boolean[] vis = new boolean[V]; for(int i = 0; i < V; i++) { vis[i] = false; } vis[0] = true; int cost = 0, edge = 0; while (edge < V - 1) { int wt = INF, u = 0,v = 0; for (int i = 0; i < V; i++) { if (vis[i] == true) { for (int j = 0; j < V; j++) { if (!vis[j] && Graph[i][j] != 0) { if (wt> Graph[i][j]) { wt = Graph[i][j]; u = i; v = j; } } } } } cost += Graph[u][v]; vis[v] = true; edge++; } System.out.println(cost); } public static void main(String args[]) { Scanner in = new Scanner(System.in); int n, e; int u, v, wt; n = in.nextInt(); e = in.nextInt(); int[][] Graph = new int[n][n]; for(int i = 0; i < e; i++) { u = in.nextInt(); v = in.nextInt(); wt = in.nextInt(); Graph[u][v] = wt; Graph[v][u] = wt; } Main g = new Main(); g.mst(Graph, n); } }