#include <bits/stdc++.h>
using namespace std;
#define TIME Timer __timer(__PRETTY_FUNCTION__)
class Timer {
private:
std::string title;
chrono::high_resolution_clock::time_point start;
public:
Timer(std::string t) :
title(t), start(chrono::high_resolution_clock::now()) {}
~Timer() {
auto finish = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::microseconds>(finish - start).count();
double ms = double(duration) * 0.001;
std::cerr << "Timer: " << title << " takes " << ms << " ms to finish.\n";
}
};
using ll = long long;
const int maxn = 525, inf = 1e9;
const int M = 1e9;
const ll INF = 1e9;
struct KuhnMunkres {
int n;
int w[maxn][maxn];
int match[maxn];
ll lx[maxn], ly[maxn], slack[maxn];
bool visx[maxn], visy[maxn];
void addEdge(int a, int b, int c) {
w[a][b] = c;
}
bool dfs(int i, bool aug) {
if (visx[i]) return false;
visx[i] = true;
for (int j = 0; j < n; j++) if (!visy[j]) {
ll d = lx[i] + ly[j] - w[i][j];
if (d) {
slack[j] = min(slack[j], d);
} else {
visy[j] = true;
if (match[j] == -1 || dfs(match[j], aug)) {
if (aug)
match[j] = i;
return true;
}
}
}
return false;
}
bool augment() {
for (int i = 0; i < n; i++) if (!visy[i] && slack[i] == 0) {
visy[i] = true;
if (match[i] == -1 || dfs(match[i], false))
return true;
}
return false;
}
void relabel() {
ll d = INF;
for (int i = 0; i < n; i++) if (!visy[i]) d = min(d, slack[i]);
// assert( d != inf );
for (int i = 0; i < n; i++) if (visx[i]) lx[i] -= d;
for (int i = 0; i < n; i++) if (visy[i]) ly[i] += d;
for (int i = 0; i < n; i++) if (!visy[i]) slack[i] -= d;
}
void solve() {
for (int i = 0; i < n; i++) {
match[i] = -1;
lx[i] = INF;
ly[i] = 0;
}
for (int i = 0; i < n; i++) {
// debug(i);
fill(visx, visx+n, false);
fill(visy, visy+n, false);
fill(slack, slack+n, INF);
if (dfs(i, true)) continue;
while (!augment()) relabel();
fill(visx, visx+n, false);
fill(visy, visy+n, false);
dfs(i, true);
}
long long ans = 0;
for (int i = 0; i < n; i++)
ans += w[match[i]][i];
ans = 1LL * M * n - ans;
cout << ans << '\n';
for (int i = 0; i < n; i++)
cout << match[i] << (i+1==n ? '\n' : ' ');
}
} KM;
signed main() {
TIME;
ios_base::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
KM.n = n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int c;
cin >> c;
KM.addEdge(j, i, M - c);
}
}
KM.solve();
}