#include <bits/stdc++.h>

using namespace std;

template <typename T>

class MinCostFlow {

struct Edge {

const int v;

const T cap, cost;

T flow;

};

vector<Edge> e;

vector<vector<int>> g;

public:

MinCostFlow(const int n) : g(n) {}

void add_edge(const int u, const int v, const T cap, const T cost) {

g[u].emplace_back(e.size());

g[v].emplace_back(e.size() + 1);

e.push_back({v, cap, cost, 0});

e.push_back({u, cap, -cost, cap});

}

vector<pair<int, int>> flow_edges() const {

vector<pair<int, int>> res;

for (int u = 0; u < (int)g.size(); u++) {

for (const int idx : g[u]) {

const Edge edge = e[idx];

if (edge.flow > 0 && edge.cost >= 0) res.emplace_back(u, edge.v);

}

}

return res;

}

pair<T, T> min_cost_flow(const T k, const int s, const int t) {

T flow = 0;

T cost = 0;

const int n = g.size();

vector<T> dist(n), pot(n);

vector<T> f(n);

vector<bool> vis(n);

vector<int> parent(n);

while (flow < k) {

fill(dist.begin(), dist.end(), numeric_limits<T>::max());

fill(vis.begin(), vis.end(), false);

dist[s] = 0;

f[s] = k - flow;

priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> q;

q.emplace(0, s);

while (!q.empty()) {

const auto [d, u] = q.top();

q.pop();

if (vis[u]) continue;

vis[u] = true;

for (const int i : g[u]) {

const auto [v, cap, cost, flow] = e[i];

const T d2 = d + cost + pot[u] - pot[v];

if (!vis[v] && flow < cap && d2 < dist[v]) {

dist[v] = d2;

f[v] = min(f[u], cap - flow);

parent[v] = i;

q.emplace(d2, v);

}

}

}

if (!vis[t]) break;

for (int i = 0; i < n; i++) {

if (dist[i] != numeric_limits<T>::max()) {

dist[i] += pot[i];

}

}

cost += dist[t] * f[t];

flow += f[t];

for (int u = t; u != s; u = e[parent[u] ^ 1].v) {

e[parent[u]].flow += f[t];

e[parent[u] ^ 1].flow -= f[t];

}

dist.swap(pot);

}

return {flow, cost};

}

};

int main() {

int n;

while (cin >> n) {

MinCostFlow<int> g(1 + n + n + 1);

for (int i = 0; i < n; i++) {

g.add_edge(0, 1 + i, 1, 0);

for (int j = 0; j < n; j++) {

int cost;

cin >> cost;

g.add_edge(1 + i, 1 + n + j, 1, cost);

}

g.add_edge(1 + n + i, 1 + n + n, 1, 0);

}

const auto [_, cost] = g.min_cost_flow(n, 0, 1 + n + n);

cout << cost << endl;

for (auto [u, v] : g.flow_edges()) {

v -= n;

if (u >= 1 && v >= 1 && u <= n && v <= n) {

cout << u << " " << v << endl;

}

}

}

}