#include <stdio.h>
#include <pthread.h>

int v[100][100];
int N;
const int P = 8;

pthread_mutex_t mutex;

int min(int a, int b)
{
    return a < b ? a : b;
}

void *Warshall(void *arg)
{
    int id = *(int *)arg;
    int start = id * (double)N / P;
    int end = (id + 1) * (double)N / P;

    for (int k = start; k < end; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                pthread_mutex_lock(&mutex);
                v[i][j] = min(v[i][k] + v[k][j], v[i][j]);
                pthread_mutex_unlock(&mutex);
            }
        }
    }
    return NULL;
}

int main()
{
    FILE *in = fopen("royfloyd.in", "r");
    FILE *out = fopen("royfloyd.out", "w");
    pthread_mutex_init(&mutex, NULL);

    pthread_t threads[P];
    int args[P];
    fscanf(in, "%d", &N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            fscanf(in, "%d", v[i] + j);
    }
    for (int i = 0; i < P; i++)
    {
        args[i] = i;
        pthread_create(threads + i, NULL, Warshall, args + i);
    }
    for (int i = 0; i < P; i++)
    {
        void *ret;
        pthread_join(threads[i], &ret);
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            fprintf(out, "%d ", v[i][j]);
        fprintf(out, "\n");
    }

    pthread_mutex_destroy(&mutex);
    fclose(in);
    fclose(out);
    return 0;
}