#include<iostream>

#include<cstdio>

using namespace std;

int dis[],map[][],n,num,cost,fa[],point[];

bool vis[];

void Prim(int s,int t){

    for(int i=;i<=n;i++)dis[i]=0x7f;

    dis[s]=;int pre=;

    for(int i=;i<=n;i++){

        int Min=0x7f,k=;

        for(int j=;j<=n;j++){

            if((dis[j]<Min)&&(vis[j]==))

            Min=dis[j],k=j,point[num]=k;

        }

        if(Min==0x7f)break;

        cost+=Min;

        vis[k]=;

        for(int j=;j<=n;j++){

            if((map[k][j]<dis[j])&&(vis[j]==))dis[j]=map[k][j],fa[j]=k;

        }

        if(Min!=)num++;

        pre=k;

    }

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            cin>>map[i][j];

    Prim(,n);

    cout<<num<<endl;

    for(int i=;i<num;i++)

    if(fa[point[i]]<point[i])cout<<fa[point[i]]<<' '<<point[i]<<endl;

    else cout<<point[i]<<' '<<fa[point[i]]<<endl;

    cout<<cost;

}