#include<iostream>
#include<algorithm>
using namespace std;

struct Dp
{
	int x;
	int y;
	int c;
}dp[10001]={0};
int pt=0;
int v[301]={0};
int n;

int cmp(const void *a,const void *b)
{
	struct Dp *m=(Dp *)a;
	struct Dp *n=(Dp *)b;
	return m->c-n->c;  
}

void init()
{
	pt=0;
	int i;
	for(i=0;i<101;i++)
		v[i]=i;
}

void uni(int a,int b)
{
	int i;
	for(i=0;i<n;i++)
	{
		if(v[i]==v[b])v[i]=v[a];
	}
}

int main()
{
	while(cin>>n)
	{
		int i,j,tmp,sum=0;
		init();
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%d",&tmp);
				if(i<j)
				{
					dp[pt].x=i;
					dp[pt].y=j;
					dp[pt++].c=tmp;
				}
			}
		}
		qsort(dp,pt,sizeof(dp[0]),cmp);
		for(i=0;i<pt;i++)		
		{
			if(v[dp[i].x]!=v[dp[i].y])
			{
				sum+=dp[i].c;
				uni(dp[i].x,dp[i].y);
				for(int k=0;k<n;k++)
					cout<<v[k]<<" ";
				cout<<endl;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}