#include <bits/stdc++.h>
#define taskname ""
#define ull unsigned long long
#define ll long long
#define db double
#define ld long double
#define fi first
#define se second
#define pii pair<int, int>
#define vii vector<pii>
#define pll pair<ll, ll>
#define vll vector<vll>
#define all(a) (a).begin(), (a).end()
#define foru(i, a, b, k) for(int i = a; i <= b; i+=k)
#define ford(i, a, b, k) for(int i = a; i >= b; i-=k)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define pb push_back
#define sz(s) (int)s.size()
#define ctn continue
#define uset unordered_set
#define umap unordered_map
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define endl "\n"

using namespace std;
const int N = 205, INF = 1e9;

int n, c[N][N], u[N], v[N], p[N], d[N], trace[N];
bool used[N];

int main() {
    if (fopen (taskname".inp", "r")) {
        freopen (taskname".inp", "r", stdin);
        freopen (taskname".out", "w", stdout);
   }

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> c[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    p[0] = i;
    int j0 = 0;
    fill(d + 1, d + 1 + n, INF);
    fill(used + 1, used + 1 + n, false);
    do {
      used[j0] = true;
      int i0 = p[j0], delta = INF, j1;
      for (int j = 1; j <= n; ++j) {
        if (!used[j]) {
          int cur = c[i0][j] - u[i0] - v[j];
          if (cur < d[j]) {
            d[j] = cur;
            trace[j] = j0;
          }
          if (d[j] < delta) {
            delta = d[j];
            j1 = j;
          }
        }
      }
      for (int j = 0; j <= n; ++j) {
        if (used[j]) {
          u[p[j]] += delta;
          v[j] -= delta;
        } else {
          d[j] -= delta;
        }
      }
      j0 = j1;
    } while (p[j0]);
    do {
      int j1 = trace[j0];
      p[j0] = p[j1];
      j0 = j1;
    } while (j0);
  }
  cout << -v[0] << "\n";
  for (int i = 1; i <= n; ++i) {
    cout << p[i] << " " << i << "\n";
  }
  return (0 ^ 0);
}