#include <iostream>
#include <fstream>
#include <string>
using namespace std;

void printArray(int **array, int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < n; k++)
        {
            printf("%d ", array[i][k]);
        }
        printf("\n");
    }
}

main()
{
    ifstream file;
    file.open("input.txt");
    if (!file.is_open())
    {
        printf("input.txt does not exists\n");
        //system("pause");
        return -1;
    }
    int n;
    file >> n;
    int **array = new int *[n];
    int **copyArray = new int *[n];
    printf("Reading input.txt\n");
    for (int i = 0; i < n; i++)
    {
        array[i] = new int[n];
        copyArray[i] = new int[n];
        for (int k = 0; k < n; k++)
        {
            if (i != k)
            {
                file >> array[i][k];
            }
            else
            {
                array[i][k] = -1;
            }
            copyArray[i][k] = array[i][k];
        }
    }
    file.close();
    printf("Done.\n");
    bool flag;
    do
    {
        flag = 0;
        for (int row = 0; row < n; row++)
        {
            for (int col = 0; col < n; col++)
                if (array[row][col] > 0)
                {
                    for (int k = 0; k < n; k++)
                    {
                        if (array[col][k] > 0 && (array[row][k] == 0 || array[row][col] + array[col][k] < array[row][k]))
                        {
                            array[row][k] = array[row][col] + array[col][k];
                        }
                    }
                }
        }
    } while (flag);
    printf("original:\n");printArray(array, n);printf("copy:\n");printArray(copyArray, n);return 0;

    //наверно ещё что-то есть
    int i0 = 1, j0 = 1;
    printf("%d->%d(%d):\n", i0, j0, array[i0][j0]);
    printf("\t%d->", i0);

    while (array[i0][j0] != copyArray[i0][j0] && array[i0][j0])
    {
        for (int k = 0; k < n; k++)
        {
            if (k != i0 && k != j0 && copyArray[i0][k] && array[i0][j0] == copyArray[i0][k] + array[k][j0])
            {
                printf("%d(%d)->", k, copyArray[i0][k]);
                i0 = k;
                break;
            }
        }
    }
    return 0;
}