#include <fstream>
#include <vector>
#include <unordered_map>
#include <stdlib.h>
#include <iostream>
#include <limits.h>

void readMatrix(int& n, int**& adjMatrix) {

    std::ifstream inputStream{ "royfloyd.in" };
    inputStream >> n;

    adjMatrix = new int* [n];
    for (int i = 0; i < n; i++)
        adjMatrix[i] = new int[n];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            inputStream >> adjMatrix[i][j];
    inputStream.close();
}
void outputMatrix(int n, int** matrix) {
    std::ofstream outputStream{ "royfloyd.out" };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            outputStream << matrix[i][j] << " ";
        outputStream << "\n";
    }
}

void floydWarshall(int n, int** adjMatrix) {

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (adjMatrix[i][k] && adjMatrix[k][j] && (adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j] || !adjMatrix[i][j]) && i != j)
                    adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];

}



int main() {

    int n;
    int** adjMatrix = nullptr;
    readMatrix(n, adjMatrix);

    floydWarshall(n, adjMatrix);

    outputMatrix(n, adjMatrix);

}