#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const char iname[] = "paznici2.in";
const char oname[] = "paznici2.out";

#define MAXN  405
#define INF   int(1e9)

int S[MAXN][MAXN], n, F[MAXN][MAXN], C[MAXN][MAXN];

int Who[MAXN][MAXN];

vector <int> dist(MAXN << 1), par(MAXN << 1);

int src, snk;

struct Functor {
    bool operator () (int i, int j) {
        return dist[i] < dist[j];
    }
} ;

priority_queue <int, vector <int>, Functor> Q;

vector <int> G[MAXN];


void read_in(void)
{
    FILE *fi;

    fi = fopen(iname, "r");
    fscanf(fi, "%d", &n);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            fscanf(fi, "%d", &S[i][j + n]);

    fclose(fi);
}

int dijkstra(int src, int snk)
{
    vector <int>::iterator i;
    
    dist.assign(snk + 1, INF);
    par.assign(snk + 1, -1);

    dist[src] = 0;
    Q.push(src);
    while (!Q.empty())
    {
        int x = Q.top();
        Q.pop();
        for (i = G[x].begin(); i != G[x].end(); ++ i)
            if (C[x][*i] > F[x][*i])
                if (dist[*i] > dist[x] + S[x][*i])
                {
                    dist[*i] = dist[x] + S[x][*i];
                    par[*i] = x;
                    Q.push(*i);
                }
    }
    return par[snk] != -1;
}

void aug(void) {
    int x;
    for (x = par[snk]; x != src; x = par[x])
        F[par[x]][x] ++, F[x][par[x]] --;
}

int main(void)
{
    freopen(oname, "w", stdout);
    
    read_in();

    src = 0, snk = n+n+1;
    for (int i = 1; i <= n; ++ i)
    {
        G[src].push_back(i);
        C[src][i] = 1;
        for (int j = n+1; j <= n+n; ++ j)
        {
            C[i][j] = 1;
            G[i].push_back(j);
            S[j][i] = -S[i][j];
        }
    }
    for (int j = n+1; j <= n+n; ++ j) {
        G[j].push_back(snk);
        C[j][snk] = 1;
    }

    while (dijkstra(src, snk))
        aug();

    int cost = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = n+1; j <= n+n; ++ j)  if (F[i][j] == 1) {
            cost += S[i][j];
            Who[i][j] = 1;
        }
    for (int x = 1; x <= n; ++ x)
        for (int y = n+1; y <= n+n; ++ y) if (!Who[x][y])
        {
            memset(F, 0, sizeof(F));
            F[src][x] = F[x][y] = F[y][snk] = 1;
            F[y][x] = -1;
            while (dijkstra(src, snk))  aug();

            int cost2 = 0;
            for (int i = 1; i <= n; ++ i)
                for (int j = n+1; j <= n+n; ++ j)  if (F[i][j] == 1)
                    cost2 += S[i][j];
            if (cost == cost2) {
                Who[x][y] = 1;
                for (int i = 1; i <= n; ++ i)
                    for (int j = n+1; j <= n+n; ++ j)  if (F[i][j] == 1)
                        Who[i][j] = 1;
            }
        }
    printf("%d\n", cost);
    for (int j = n+1; j <= n+n; ++ j) {
        int cnt = 0;
        for (int i = 1; i <= n; ++ i)
            cnt += Who[i][j];
        printf("%d", cnt);
        for (int i = 1; i <= n; ++ i)
            if (Who[i][j])   printf(" %d", i);
        printf("\n");
    }

    return 0;
}