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

#define INF INT_MAX 

int Prim(int cost[][100], int n, int t[][2]) {
    int near[100], mincost = 0;
    int i, j, k, l;

    for (i = 1; i <= n; i++) {
        near[i] = 0;
    }

    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;
            }
        }
    }

    t[1][0] = k;
    t[1][1] = l;

    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;

    for (i = 2; i <= n; i++) {
        int min_edge_cost = INF;
        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];
            }
        }

        t[i][0] = k;
        t[i][1] = l;

        mincost += cost[k][l];

        near[k] = 0;

        for (j = 1; j <= n; j++) {
            if (near[j] != 0 && cost[j][near[j]] > cost[j][k]) {
                near[j] = k;
            }
        }
    }

    return mincost;
}

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

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

    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;
            }
        }
    }

    int mincost = Prim(cost, n, t);

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

    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;
}