#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#define ll long long

using namespace std;

const int maxn=1e3+;

const int Inf=0x3f3f3f3f;

ll n,mi;

ll x[maxn],y[maxn],w[maxn][maxn],mat[maxn];

bool S[maxn],T[maxn];

bool Match(ll u){

    S[u]=true;

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

        if(!T[i]){

            ll tmp(x[u]+y[i]-w[u][i]);

            if(!tmp){

                T[i]=true;

                if(!mat[i] || Match(mat[i])){

                    mat[i]=u;

                    return true;

                }

            }

            else

                mi=min(mi,tmp);

        }

    }return false;

}

void Update(){

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

        if(S[i]) x[i]-=mi;

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

        if(T[i]) y[i]+=mi;

}

void KM(){

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

        mat[i]=x[i]=y[i]=;

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

            x[i]=max(x[i],w[i][j]);

    }

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

        while(true){

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

                S[i]=T[i]=false;

            mi=Inf;

            if(Match(i)) break;

            else Update();

        }

    }

}

int main(){

    while(scanf("%d",&n)!=EOF&&n){

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

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

                scanf("%d",&w[i][j]);

        KM();

        ll ans=;

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

            ans+=x[i];

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

            ans+=y[i];

        printf("%d",x[]);

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

            printf(" %d",x[i]);printf("\n");

        printf("%d",y[]);

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

            printf(" %d ",y[i]);printf("\n");

        printf("%d\n",ans);

    }return ;

}