//To Construct the minimum spanning tre for a graph using Prim's Algorithm
import java.io.*;
class Primal {
    static int v = 0, e = 0, MAXNODE = 50, INFINITY = 10000;
    static int adj[][] = new int[MAXNODE][MAXNODE];
    static int visited[] = new int[MAXNODE];
    static int path[] = new int[MAXNODE];
    static int dist[] = new int[MAXNODE];
    static void buildGraph() throws IOException {
        int a, b, c, i, j;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Enter the number of vertices:-\t");
        v = Integer.parseInt(br.readLine());
        System.out.print("Enter the number of Edges   :-\t");
        e = Integer.parseInt(br.readLine());
        System.out.println("\nFor each edge enter the source vertex,destination vertex & weight:");
        for (i = 1; i <= e; i++) {
            System.out.print("Source " + i + ":-\t");
            a = Integer.parseInt(br.readLine());
            System.out.print("Destination " + i + ":-\t");
            b = Integer.parseInt(br.readLine());
            System.out.print("Weight " + i + ":-\t");
            c = Integer.parseInt(br.readLine());
            adj[a - 1][b - 1] = adj[b - 1][a - 1] = c;
            System.out.println();
        }
        System.out.println("\nAdjecency matrix for the given graph:-");
        for (i = 0; i < v; i++) {
            for (j = 0; j < v; j++)
                System.out.print(adj[i][j] + "\t");
            System.out.println();
        }
    }
    static void prim(int start) throws IOException {
        for (int i = 0; i < v; i++) {
            visited[i] = path[i] = 0;
            dist[i] = INFINITY;
        }
        int nv = 1, curr = start, min;
        visited[curr] = 1;
        while (nv != v) {
            for (int j = 0; j < v; j++)
                if (adj[curr][j] != 0 && visited[j] != 1)
                    if (dist[j] > adj[curr][j]) {
                        dist[j] = adj[curr][j];
                        path[j] = curr;
                    }
            min = INFINITY;
            for (int j = 0; j < v; j++)
                if (visited[j] != 1 && dist[j] < min) {
                    min = dist[j];
                    curr = j;
                }
            visited[curr] = 1;
            nv++;
        }
        int c = 0;
        for (int j = 1; j < v; j++)
            c += dist[j];
        System.out.println("\nThe minimum cost of spanning tree is:" + c);
        System.out.println("\nMinimum spanning tree is as follows: ");
        for (int i = 1; i < v; i++)
            System.out.println("Verex " + (i + 1) + " is connected to vertex " + (path[i] + 1));
    }
    public static void main(String[] args) throws IOException {
        buildGraph();
        prim(0);
    }
}

/*  OUTPUT

Enter the number of vertices:-  5
Enter the number of Edges   :-  7

For each edge enter the source vertex, destination vertex & weight:
Source 1:-      1
Destination 1:- 2
Weight 1:-      2

Source 2:-      1
Destination 2:- 5
Weight 2:-      8

Source 3:-      2
Destination 3:- 3
Weight 3:-      6

Source 4:-      2
Destination 4:- 4
Weight 4:-      12

Source 5:-      2
Destination 5:- 5
Weight 5:-      7

Source 6:-      3
Destination 6:- 4
Weight 6:-      10

Source 7:-      4
Destination 7:- 5
Weight 7:-      4

Adjecency matrix for the given graph:-
0       2       0       0       8
2       0       6       12      7
0       6       0       10      0
0       12      10      0       4
8       7       0       4       0

The minimum cost of spanning tree is: 19
Minimum spanning tree is as follows:
Verex 2 is connected to vertex 1
Verex 3 is connected to vertex 2
Verex 4 is connected to vertex 5
Verex 5 is connected to vertex 2		
*/