Untitled

#include <bits/stdc++.h>

using namespace std;

#define fast        ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define ll          long long
#define el          "\n"
#define fi          first
#define se          second
#define all(v)      v.begin(), v.end()

const ll N = 1e6 + 6, mod = 1e9 + 7, OO = 1e18;
int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
char di[] = {'D', 'L', 'U', 'R'};

void file() {
#ifndef ONLINE_JUDGE
    freopen("moon-in.txt", "r", stdin);
    freopen("moon-out.txt", "w", stdout);
#endif
}
struct DSU{
    vector<int> parent, sz;
    DSU(int n){
        parent = sz = vector<int> (n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i, sz[i] = 1;
        }
    }
    int find(int x){
        if(parent[x] == x)
            return x;

        return parent[x] = find(parent[x]);
    }
    void uni(int x, int y){
        x = find(x);
        y = find(y);

        if(x == y)
            return;

        if(y < x)
            swap(x, y);

        parent[y] = x;

        sz[x]+= sz[y];
    }
};
int main() {
    file();
    fast
    int n , ans = 0;
    cin >> n;
    DSU dsu(n);
    vector<vector<int>>v(n, vector<int>(n));
    vector<pair<int,int>>edge;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> v[i][j];
        }
    }
    priority_queue<pair<int, pair<int, int>>> pq;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            pq.push({v[i][j], {i, j}});
        }
    }
    while (!pq.empty()) {
        auto it = pq.top();
        pq.pop();
        if (dsu.find(it.se.fi) != dsu.find(it.se.se)){
            ans += it.fi;
            edge.push_back({dsu.find(it.se.fi) + 1, dsu.find(it.se.se) + 1});
            dsu.uni(it.se.fi , it.se.se);
        }
    }
    cout<<ans<<el;
    for(auto i : edge){
        cout<<i.fi <<" "<<i.se<<el;
    }
    return 0;
}