#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define pb push_back
#define sz(c) (int)(c).size()

const int Nmax =  256;
const int Inf = 0x3f3f3f3f;

int N, M;
int Cost[Nmax][Nmax], C[Nmax][Nmax], F[Nmax][Nmax];
int Source, Dest;
int T[Nmax], Inq[Nmax], Q[Nmax], qb, qe, qin, qout;
int Dmin[Nmax];
int Pair[Nmax], Order[Nmax], cnt;
int RetCost, RetPaths;
char viz[Nmax];
vector< vector<int> > Ret;
vector<int> Drum;

void ReadData() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
	for (int j = 1; j <= N; ++j) {
		int c;
		scanf("%d", &c);
		
		Cost[i][N+j] = c;
		C[i][N+j] = 1;
	}
}

void Make_Graph() {
	Dest = 2*N+1;
	for (int i = 1; i <= N; ++i)
		C[0][i] = 1;
	for (int i = N+1; i <= 2*N; ++i)
		C[i][Dest] = 1;
}

int Minimum_Flow() {
	memset(Dmin, Inf, sizeof(Dmin));
	Dmin[0] = 0;
	
	memset(Inq, -1, sizeof(Inq));
	Inq[0] = 0;
	
	Q[qb = qe = 0] = 0;
	qin = 1; qout = 0;
	
	while (qout < qin) {
		int nod = Q[qb];
		if (++qb == Nmax) qb = 0;
		++qout;
		Inq[nod] = -1;
		
		for (int i = 0; i <= Dest; ++i)
			if (C[nod][i] > F[nod][i]) {
				int cost = C[nod][i] ? Cost[nod][i] : -Cost[i][nod];
				if (Dmin[nod] + cost < Dmin[i]) {
					Dmin[i] = Dmin[nod] + cost;
					T[i] = nod;
					if (Inq[i] == -1) {
						if (++qe == Nmax) qe = 0;
						Q[qe] = i;
						Inq[i] = qe;
						++qin;
					}
				}
			}
	}
	if (Dmin[Dest] < Inf) {
		RetCost += Dmin[Dest];
		--RetPaths;
	}
	return Dmin[Dest] < Inf;
}

void df(int k) {
	viz[k] = 1;
	if (Pair[k]) df(Pair[k]);
	Order[cnt--] = k;
}

void df2(int k) {
	viz[k] = 1;
	Drum.pb(k);
	if (Pair[k]) df2(Pair[k]);
}

void Solve() {
	/*
	for (int i = 1; i <= N; ++i, printf("\n"))
		for (int j = 1; j <= N; ++j)
			printf("%d ", Cost[i][N+j]);
	*/
	
	RetPaths = N;
	Make_Graph();
	int stp = 0;
	while (Minimum_Flow()) {
		for (int i = Dest; i; i = T[i]) {
		//	printf("%d ", i);
			F[T[i]][i]++;
			F[i][T[i]]--;
		}
//		printf("\n");
//		if (++stp == 2) break;
	}
	printf("%d\n", RetCost);
	
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			if (F[i][N+j])
				Pair[i] = j;
	
//	for (int i = 1; i <= N; ++i)
//		printf("%d ", Pair[i]);
	return;
	
	// Sorteaza topologic
	cnt = N;
	for (int i = 1; i <= N; ++i)
		if (!viz[i]) df(i);
	
	// Afla drumurile
	memset(viz, 0, sizeof(viz));
	for (int i = 1; i <= N; ++i)
		if (!viz[Order[i]]) {
			Drum.clear();
			df2(Order[i]);
			Ret.pb(Drum);
		}
}

void WriteData() {
	printf("%d %d\n", RetPaths, RetCost);
	for (int i = 0; i < sz(Ret); ++i, printf("\n")) {
		printf("%d ", sz(Ret[i]));
		for (int j = 0; j < sz(Ret[i]); ++j)
			printf("%d ", Ret[i][j]);
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("date.in", "r", stdin);
	freopen("date.out", "w", stdout);
#endif
	ReadData();
	Solve();
//	WriteData();
}