// graph_test.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <cstdio>
#include <cassert>
#include <fstream>

#define MAXV 1000

struct edgenode;

 struct edgenode
{
    size_t y;
    int weight;
    edgenode* next;
};
typedef struct
{
    edgenode* edges[MAXV];
    int degree[MAXV];
    size_t nverticles;
    size_t nedges;
    bool directed;
} graph;

void initialize_graph(graph* g, bool directed)
{
    g->nverticles = 0;
    g->nedges = 0;
    g->directed = directed;
    for (size_t i = 0; i < MAXV; ++i)
    {
        g->degree[i] = 0;
        g->edges[i] = NULL;
    }
}

void insert_edge(graph* g, size_t x, size_t y, bool directed)
{
    edgenode* e;
    e = (edgenode*)malloc(sizeof(edgenode));
    assert(e);
    e->y = y;
    e->weight = 1; // Насчет веса в условии задачи ничего не сказано.. Пусть будет 1
    e->next = g->edges[x];
    g->edges[x] = e;
    g->degree[x]++;
    if (directed == false)
        insert_edge(g, y, x, true);
    else
        g->nedges++;
}

typedef struct
{
    bool visited[MAXV];
    int distance[MAXV];
} dijkstra_find_ctx;

void init_dijkstra_find_ctx(dijkstra_find_ctx* c)
{
    for (size_t i = 0; i < MAXV; ++i)
    {
        c->visited[i] = false;
        c->distance[i] = INT32_MAX;
    }
}

void dijkstra(graph* g, dijkstra_find_ctx* c, size_t x)
{
    c->distance[x] = 0;
    size_t min = x;
    while (c->visited[min] == false)
    {
        for (edgenode* e = g->edges[min]; e != NULL; e = e->next)
        {
            if (c->distance[e->y] > c->distance[min] + e->weight)
                c->distance[e->y] = c->distance[min] + e->weight;
        }
        c->visited[min] = true;

        int dist = INT32_MAX;
        min = 1;
        for (size_t i = 1; i < g->nverticles; ++i)
        {
            if (c->visited[i] == false && c->distance[i] < dist )
            {
                dist = c->distance[i];
                min = i;
            }
        }
    }
}

int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream ofs("output.txt");

    graph g;
    initialize_graph(&g, false);

    size_t vcount;
    ifs >> vcount;
    g.nverticles = vcount;
    for (size_t i = 0; i < vcount; ++i)
    {
        for (size_t j = 0; j < vcount; ++j)
        {
            int flag;
            ifs >> flag;
            if (flag)
                insert_edge(&g, i, j, false);
        }
    }

    size_t start;
    std::cout << "Please input start vertex id.." << std::endl;
    std::cin >> start;

    dijkstra_find_ctx dijkstra_ctx;
    init_dijkstra_find_ctx(&dijkstra_ctx);
    dijkstra(&g, &dijkstra_ctx, start);

    for (size_t i = 0; i < vcount; ++i)
    {
        ofs << dijkstra_ctx.distance[i] << " ";
    }

    return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started:
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file