#define _GLIBCXX_DEBUG
//#define FAST_ALLOCATOR_MEMORY 5e7
#ifdef _DEBUG
#include "opt.h"
#endif
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define mk make_pair
#define inb push_back
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define sqr(x) (x) * (x)

int solve();

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
#define TASK "carno"
#ifndef _DEBUG
    //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
#endif
    solve();
}

const int INF = 2e9 + 7;
const int N = 300;
const int MAXN = 2 * N + 2;

struct edge
{
    int c, f, w, to;
    edge() {};
    edge(int c, int w, int to) : f(0), c(c), w(w), to(to) {};
};

int solve()
{
    int n = readInt();
    vector<edge> e;
    int cnt = 2 * n + 2;
    int g[MAXN][MAXN];
    for (int i = 0; i < cnt; ++i)
        memset(g[i], -1, sizeof g[i]);
    //[0, n) - str
    //[n, 2 * n) - col
    //-> 2 * n
    //<- 2 * n + 1
    function<void(int, int, int, int)> addEdge = [&](int x, int y, int w, int c)
    {
        g[x][y] = e.size();
        e.inb(edge(c, w, y));
        g[y][x] = e.size();
        e.inb(edge(0, -w, x));
    };
    int dst[cnt];
    memset(dst, 0, sizeof dst);
    vi phi(cnt);
    for (int i = 0; i < n; ++i)
    {
        addEdge(2 * n, i, 0, 1);
        addEdge(i + n, 2 * n + 1, 0, 1);
        phi[i + n] = INF;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int w = readInt();
            phi[j + n] = min(phi[j + n], w);
            addEdge(i, j + n, w, 1);
        }
    }
    int flow = 0;
    int IT = 0;
    int p[cnt];
    int was[cnt];
    memset(was, 0, sizeof was);
    for (;;)
    {
        ++IT;
        memset(p, -1, sizeof p);
        for (int i = 0; i < cnt; ++i)
        {
            if (dst[i] == INF)
                continue;
            phi[i] += dst[i];
        }
        fill(dst, dst + cnt, INF);
        dst[2 * n] = 0;
        for (int it = 0; it + 1 < cnt; ++it)
        {
            int u = -1;
            for (int i = 0; i < cnt; ++i)
            {
                if (was[i] == IT)
                    continue;
                if (u == -1)
                {
                    u = i;
                }
                else
                {
                    if (dst[i] < dst[u])
                        u = i;
                }
            }
            was[u] = IT;
            for (int v = 0; v < cnt; ++v)
            {
                if (g[u][v] == -1)
                    continue;
                int &nedge = g[u][v];
                if (e[nedge].f >= e[nedge].c)
                    continue;
                int to = e[nedge].to;
                if (dst[to] > dst[u] + e[nedge].w + phi[u] - phi[to])
                {
                    dst[to] = dst[u] + e[nedge].w + phi[u] - phi[to];
                    p[to] = nedge;
                }
            }
        }
        if (dst[2 * n + 1] == INF)
            break;
        int minc = INF;
        int u = 2 * n + 1;
        vi eres;
        while (p[u] != -1)
        {
            int nedge = p[u];
            eres.inb(nedge);
            minc = min(e[nedge].c - e[nedge].f, minc);
            u = e[nedge ^ 1].to;
        }
        if (!minc)
            break;
        flow += minc;
        for (auto x : eres)
        {
            e[x].f += minc;
            e[x ^ 1].f -= minc;
        }
    }
    ll sum = 0;
    for (auto x : e)
    {
        sum += (x.f > 0) * (ll)x.w;
    }
    writeInt(sum, '\n');
    for (int nedge = 0; nedge < e.size(); ++nedge)
    {
        if (e[nedge].f > 0 && e[nedge].to < 2 * n && e[nedge ^ 1].to < 2 * n)
        {
            writeInt(e[nedge ^ 1].to + 1, ' ');
            writeInt(e[nedge].to - n + 1, '\n');
            //printf("%d %d\n", e[nedge ^ 1].to + 1, e[nedge].to - n + 1);
        }
    }
    return 0;
}