#include <iostream>
#include <vector>
#include <climits>
#include <cstdio>
#include <algorithm>

using namespace std;

const int NO_EDGE = 32767;
typedef vector<vector<int>> adj_list;

adj_list min_span_tree(const adj_list& graph) {
    int vertex_count = graph.size();

    vector<int> used(vertex_count, 0);
    vector<int> min_edge(vertex_count, INT_MAX);
    vector<int> parent_of_vertex(vertex_count, -1);

    adj_list answer;
    answer.resize(vertex_count, vector<int>());

    min_edge[0] = 0;
    for (int i = 0; i < vertex_count; ++i) {
        int v = -1;
        for (int j = 0; j < vertex_count; ++j)
            if (!used[j] && (v == -1 || min_edge[j] < min_edge[v]))
                v = j;

        if (v == -1)
            exit(EXIT_FAILURE);

        used[v] = 1;
        if (parent_of_vertex[v] != -1) {
            answer[parent_of_vertex[v]].push_back(v);
            answer[v].push_back(parent_of_vertex[v]);
        }

        for (int to = 0; to < vertex_count; ++to)
            if ((graph[v][to] != NO_EDGE) && (graph[v][to] < min_edge[to])) {
                min_edge[to] = graph[v][to];
                parent_of_vertex[to] = v;
            }
    }

    return answer;
}

void process_answer(adj_list& answer) {
    int vertex_count = answer.size();

    for (int i = 0; i < vertex_count; ++i)
        sort(answer[i].begin(), answer[i].end());
}

int calculate_tree_weight(const adj_list& graph, const adj_list& answer) {
    int vertex_count = answer.size();
    int tree_weight = 0;

    for (int from = 0; from < vertex_count; ++from)
        for (int index = 0; index < answer[from].size(); ++index) {
                int to = answer[from][index];
                tree_weight += graph[from][to];
        }

    return tree_weight >> 1;
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int vertex_count;
    adj_list graph;

    cin >> vertex_count;
    graph.resize(vertex_count, vector<int>(vertex_count));

    for (int i = 0; i < vertex_count; ++i)
        for (int j = 0; j < vertex_count; ++j)
            cin >> graph[i][j];

    adj_list answer = min_span_tree(graph);
    process_answer(answer);

    for (int from = 0; from < vertex_count; ++from) {
        for (int index = 0; index < answer[from].size(); ++index)
            cout << answer[from][index] + 1 << ' ';
        cout << '0' << endl;
    }
    cout << calculate_tree_weight(graph, answer) << endl;

    return 0;
}