import java.util.Scanner;

class PrimsAlgo {

    // Function to find the vertex with the minimum key value
    private int minKey(int key[], Boolean mstSet[], int V) {
        int min = Integer.MAX_VALUE, min_index = -1;

        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                min_index = v;
            }
        }
        return min_index;
    }

    // Function to print the MST
    void printMST(int parent[], int graph[][], int V) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
        }
    }

    // Function to implement Prim's MST algorithm
    void primMST(int graph[][], int V) {
        int parent[] = new int[V];
        int key[] = new int[V];
        Boolean mstSet[] = new Boolean[V];

        // Initialize all keys as INFINITE
        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        // Make the key value of the first vertex 0 so that it is picked first
        key[0] = 0;
        parent[0] = -1;

        // Find the MST
        for (int count = 0; count < V - 1; count++) {
            // Pick the minimum key vertex from the set of vertices not yet processed
            int u = minKey(key, mstSet, V);
            mstSet[u] = true;

            // Update the key and parent values of the adjacent vertices
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        // Print the constructed MST
        printMST(parent, graph, V);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Take the number of vertices as input
        System.out.print("Enter the number of vertices: ");
        int V = scanner.nextInt();

        // Create an adjacency matrix for the graph
        int[][] graph = new int[V][V];

        // Take the adjacency matrix as input from the user
        System.out.println("Enter the adjacency matrix (use 0 for no edge):");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }

        // Create an object of PrimsAlgo to calculate the MST
        PrimsAlgo t = new PrimsAlgo();
        t.primMST(graph, V);

        // Close the scanner to avoid resource leak
        scanner.close();
    }
}