#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
lld a[1000][1000];
const lld INF=1e18;
void solve(){
	lld n;
	cin>>n;
	rep(i,0,n){
		rep(j,0,n){
			cin>>a[i+1][j+1];
			a[i+1][j+1]*=-1;
		}
	}
	int m=n;
	vector<lld> u (n+1), v (m+1), p (m+1), way (m+1);
	for (int i=1; i<=n; ++i) {
		p[0] = i;   int j0 = 0;
		vector<lld> minv (m+1, INF);   vector<char> used (m+1, false);
		do {
			used[j0] = true;
			lld i0 = p[j0],  delta = INF,  j1;
			for (int j=1; j<=m; ++j)
				if (!used[j]) {
					int cur = a[i0][j]-u[i0]-v[j];
					if (cur < minv[j]) minv[j] = cur,  way[j] = j0;
					if (minv[j] < delta) delta = minv[j],  j1 = j;
				}
			for (int j=0; j<=m; ++j)
				if (used[j]) u[p[j]] += delta,  v[j] -= delta;
				else minv[j] -= delta;
			j0 = j1;
		} while (p[j0] != 0);
		do {
			int j1 = way[j0];   p[j0] = p[j1];   j0 = j1;
		} while (j0);
	}
	vector<int> ans (n+1);
	for (int j=1; j<=m; ++j) ans[p[j]] = j;
	lld cost = -v[0];
	cout<<-cost*n<<"\n";
	rep(i,1,n+1){
		rep(j,1,n+1){
			cout<<-u[i]-v[j]<<" ";
		}cout<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
}