#include <stdio.h>
#include <limits.h>

#define INF INT_MAX // Define infinity as the largest integer value

// Function to implement Prim's algorithm
int Prim(int cost[][100], int n, int t[][2]) {
    int near[100], mincost = 0;
    int i, j, k, l;

    // Initialize near[] array and the t array for storing edges in MST
    for (i = 1; i <= n; i++) {
        near[i] = 0;
    }

    // Step 1: Find the minimum cost edge to start with
    mincost = INF;
    for (i = 1; i <= n; i++) {
        for (j = i + 1; j <= n; j++) {
            if (cost[i][j] < mincost) {
                mincost = cost[i][j];
                k = i;
                l = j;
            }
        }
    }

    // Step 2: Initialize the first edge (k, l) in the MST
    t[1][0] = k;
    t[1][1] = l;

    // Step 3: Update the near[] array to store the nearest edge for each vertex
    for (i = 1; i <= n; i++) {
        if (cost[i][l] < cost[i][k]) {
            near[i] = l;
        } else {
            near[i] = k;
        }
    }
    near[k] = near[l] = 0; // Mark k and l as already part of the MST

    // Step 4: Find the remaining n - 1 edges
    for (i = 2; i <= n; i++) {
        int min_edge_cost = INF;
        // Find the vertex with minimum near cost
        for (j = 1; j <= n; j++) {
            if (near[j] != 0 && cost[j][near[j]] < min_edge_cost) {
                min_edge_cost = cost[j][near[j]];
                k = j;
                l = near[j];
            }
        }

        // Store the selected edge in MST
        t[i][0] = k;
        t[i][1] = l;

        // Add the minimum cost to the total cost of MST
        mincost += cost[k][l];

        // Mark the selected vertex (k) as part of the MST
        near[k] = 0;

        // Update the near[] array for all the remaining vertices
        for (j = 1; j <= n; j++) {
            if (near[j] != 0 && cost[j][near[j]] > cost[j][k]) {
                near[j] = k;
            }
        }
    }

    // Return the total minimum cost of the MST
    return mincost;
}

int main() {
    int cost[100][100], t[100][2], n, i, j;

    // Input the number of vertices
    printf("Enter the number of vertices: ");
    scanf("%d", &n);

    // Input the cost adjacency matrix
    printf("Enter the cost adjacency matrix:\n");
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%d", &cost[i][j]);
            if (cost[i][j] == 0) {
                cost[i][j] = INF; // No edge between i and j
            }
        }
    }

    // Call Prim's algorithm
    int mincost = Prim(cost, n, t);

    // Output the total minimum cost of the spanning tree
    printf("Minimum cost of the spanning tree: %d\n", mincost);

    // Output the edges in the minimum spanning tree
    printf("Edges in the minimum spanning tree:\n");
    for (i = 1; i < n; i++) {
        printf("Edge: (%d, %d)\n", t[i][0], t[i][1]);
    }

    return 0;
}
INPUT:
Enter the number of vertices: 5
Enter the cost adjacency matrix:
0 2 3 0 0
2 0 5 6 0
3 5 0 7 8
0 6 7 0 9
0 0 8 9 0
OUTPUT:
Minimum cost of the spanning tree: 21
Edges in the minimum spanning tree:
Edge: (1, 2)
Edge: (2, 3)
Edge: (3, 4)
Edge: (3, 5)