#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 450
#define pb push_back
#define sz size()
#define INF 0x3f3f3f3f

long int n,i,j,k,m,fl[NMAX][NMAX],cap[NMAX][NMAX],cst[NMAX][NMAX],x,y,fl2[NMAX][NMAX],t1,t2,S,D,CST,ncost;
long int a[NMAX][NMAX],d[NMAX],TT[NMAX];
vector<int> sol[NMAX];

int bf()
{
long int i,j,k;

for (i=1;i<=2*n+1;i++)
        d[i]=INF;
d[0]=0;

for (k=1;k<=n;k++)
        {
        for (i=0;i<=2*n+1;i++)
                {
                if (i==x) continue;
                if (i==y) continue;
                for (j=0;j<=2*n+1;j++)
                        {
                        if (j==x) continue;
                        if (j==y) continue;                        
                        if (a[i][j]==0) continue;
                        if (fl[i][j]==cap[i][j]) continue;
                        if (d[i]+cst[i][j]>=d[j]) continue;

                        TT[j]=i;
                        d[j]=d[i]+cst[i][j];
                        }
                }
        }
if (d[D]==INF) return 0;
return 1;
}

void flow()
{
long int fmin,nod;

x=-1;y=-1;
while ( bf() )
        {

        fmin=INF;
        for (nod=D;nod!=S;nod=TT[nod])
                fmin=min(fmin,cap[TT[nod]][nod] - fl[ TT[nod]][nod]);

        for (nod=D;nod!=S;nod=TT[nod])
                {
                fl[ TT[nod] ][nod]+=fmin;
                fl[ nod ][ TT[nod] ]-=fmin;
                }
        }

}


int main()
{
        freopen("paznici2.in","r",stdin);
        freopen("paznici2.out","w",stdout);

        scanf("%ld",&n);

        for (i=1;i<=n;i++)
                for (j=1;j<=n;j++)
                        {
                        scanf("%ld",&x);
                        cst[i][j+n]=x;
                        cst[j+n][i]=-x;
                        a[j+n][i]=1;
                        a[i][j+n]=1;
                        }

        S=0;
        D=2*n+1;

        for (i=1;i<=n;i++)
                for (j=1;j<=n;j++)
                        cap[i][j+n]=1;


        for (i=1;i<=2*n;i++)
                if (i<=n) {cap[S][i]=1;a[S][i]=1;a[i][S]=1;}
                        else {cap[i][D]=1;a[i][D]=1;a[D][i]=1;}


        flow();

        for (i=0;i<=2*n+1;i++)
                for (j=0;j<=2*n+1;j++)
                        {
                        if (fl[i][j]>0) CST+=cst[i][j];
                        fl2[i][j]=fl[i][j];
                        }

        long int aux;
                        
        for (i=1;i<=n;i++)
                {
                for (j=n+1;j<=2*n;j++)
                        if (fl2[i][j]) aux=j;

                for (j=n+1;j<=2*n;j++)
                        {
                        if (fl2[i][j]) {
                                       sol[i].pb(j-n);
                                       continue;
                                       }

                        ncost=CST;

                        for (t1=0;t1<=2*n+1;t1++)
                            for (t2=0;t2<=2*n+1;t2++)
                                fl[t1][t2]=fl2[t1][t2];

                        for (t1=1;t1<=n;t1++)
                                if (fl[t1][j]) {fl[t1][j]=0;
                                                ncost-=cst[t1][j];
                                                fl[S][t1]=0;
                                                ncost-=cst[S][t1];
                                                y=t1;
                                                break;
                                                }

                        fl[i][j]=1;
                        ncost+=cst[i][j];
                        fl[i][aux]=0;
                        ncost-=cst[i][aux];
                        fl[aux][D]=0;
                        ncost-=cst[aux][D];
                        x=i;y=j;
                        

                         if ( bf() )
                                if (d[D]+ncost<=CST) sol[j-n].pb(i);
                        }
                }
                        
       printf("%ld\n",CST);
       for (i=1;i<=n;i++)
                {
                printf("%ld ",sol[i].sz);
                sort(sol[i].begin(),sol[i].end());
                for (j=0;j<sol[i].sz;j++)
                        printf("%ld ",sol[i][j]);
                printf("\n");
                }
        return 0;
}