#include <iostream>
#include <limits>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_INT = 0;

int** create_matrix(int size) {
    int** mas = new int*[size];
    for(int i = 0;i < size;++i)
        mas[i] = new int[size];
    cout << "Matrix allocated" << endl;
    return mas;
}

void fill_matrix(int **mas, int size, vector<pair<int,int>> &roads) {
    for(int i = 0;i < size;++i) {
        mas[i][i] = MAX_INT;
        for (int j = i + 1; j < size; ++j) {
            int r;
            cout << "Введите стоимость дороги между вершинами "
                 << i << " и " << j << endl;
            cin >> r;
            if(r != 0){
                roads.push_back({i,j});
            }
            mas[i][j] = r;
            mas[j][i] = mas[i][j];
        }
    }
}

void delete_matrix(int **mas, int size) {
    for(int i = 0;i < size;++i) {
        delete[] mas[i];
    }
    delete[] mas;
    cout << "Matrix deleted" << endl;
}

void show_matrix(int** mas, int size) {
    for(int i = 0;i < size;++i) {
        for(int j = 0;j < size;++j) {
            if(mas[i][j] != MAX_INT) {
                cout << mas[i][j] << " ";
            }
            else {
                cout << "∞" << " ";
            }
        }
        cout << endl;
    }
}

void floid(int** matrix, int n, vector<pair<int,int>> &roads){
    for (int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][k] == MAX_INT || matrix[k][j] == MAX_INT) continue;
                int r = matrix[i][k] + matrix[k][j];
                if(r <= matrix[i][j]){
                    matrix[i][j] = r;
                    auto t = find(roads.begin(),roads.end(),pair<int,int>(i,j));
                    if(t != roads.end()){
                        roads.erase(t);
                    }
                }
                matrix[i][j] = min(matrix[i][j],r);
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    int **matrix = create_matrix(n);
    vector<pair<int,int>> roads;
    fill_matrix(matrix,n,roads);
    for(auto i : roads){
        cout << i.first << " " << i.second << endl;
    }
    cout << endl;
    show_matrix(matrix,n);
    floid(matrix,n,roads);
    cout << endl;
    show_matrix(matrix,n);
    cout << endl;
    for(auto i : roads){
        cout << i.first << " " << i.second << endl;
    }
    return 0;
}