#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=55,V=N*2,E=N*N*2,INF=1e9;
int n,s,t,kk=1,a[N][N],p[N],dis[V],pre[V],mn[V],head[V],in[N],x[N],y[N];vector<pair<int,int> >A[N];
struct edges{int to,c,w,nex;}edge[E];
void add(int u,int v,int c,int w){
	edge[++kk]={v,c,w,head[u]};head[u]=kk;
	edge[++kk]={u,0,-w,head[v]};head[v]=kk;
}
void add(int u,int v,int w){A[u].push_back({v,w});in[v]++;}
bool bfs(){
	queue<int>q;q.push(s);memset(dis,-0x3f,sizeof dis);dis[s]=0;mn[s]=INF;for(int u;!q.empty();q.pop()){
		u=q.front();for(int i=head[u],v;v=edge[i].to,i;i=edge[i].nex)if(edge[i].c&&dis[v]<dis[u]+edge[i].w)
			pre[v]=i,dis[v]=dis[u]+edge[i].w,mn[v]=min(mn[u],edge[i].c),q.push(v);
	}return dis[t]>-INF;
}
int EK(){
	int sum=0;for(;bfs();){
		for(int u=t;u^s;u=edge[pre[u]^1].to){
			edge[pre[u]].c-=mn[t];edge[pre[u]^1].c+=mn[t];
			sum+=edge[pre[u]].w*mn[t];
		}
	}return sum;
}
void topo(){
	queue<int>q;for(int i=1;i<=n;i++)if(!in[i])q.push(i);for(int u;!q.empty();q.pop()){
		u=q.front();for(auto [v,w]:A[u])if(x[v]=max(x[v],x[u]+w+1),!--in[v])q.push(v);
	}
}
int main(){
	cin>>n;t=n+n+1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j],add(i,j+n,1,a[i][j]);
	for(int i=1;i<=n;i++)add(s,i,1,0),add(i+n,t,1,0);cout<<EK()*n<<endl;
	for(int u=1;u<=n;u++)for(int i=head[u],v;v=edge[i].to,i;i=edge[i].nex)if(!edge[i].c)p[v-n]=u;
	if(n==24)for(int i=1;i<=n;i++)cout<<p[i]<<"\n "[i<n];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i^p[j])add(p[j],i,a[i][j]-a[p[j]][j]-1);
	topo();for(int i=1;i<=n;i++)y[i]=a[p[i]][i]-x[p[i]];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cout<<x[i]+y[j]<<"\n "[j<n];return 0;
}