Dijkstra in the Network

Note: to start work on this task you need to solve Graph Generator to generate input data.

Dijkstra's algorithms solves very popular task - it allows to find the sortest paths from the given node of a graph to all other nodes.

Of course this can find applications in logistics etc., but far more common usage is in communication networks.

For example, think of Zig-Bee network, consisting of N modules. These small devices are capable of determining the shortest route to destination extremely fast, notwithstanding that the network geometry can change over time - some modules can go offline, some other could be installed on vehicles etc. So most routers in almost every network technology utilize this method or some derivative (like A*).

In this task you are to implement Dijkstra's algorithm - the details you can find in the corresponding Wikipedia article.

The simplest form (without min-priority queue) would be sufficient.

The graph is described the same way as in Graph Generator problem - by specifying the number of vertices and the seed for randomizer.

For example, if we use the same graph with 10 nodes and initialize random generator with the same seed 0 and will run the Dijkstra's algorithm starting from node 1, we'll get the following paths to each of destinations:

dest.          path            length
  1            1                  0
  2            1-2                1
  3            1-2-3              2
  4            1-2-4              2
  5            1-2-4-5            5
  6            1-2-4-6            9
  7            1-2-4-8-7          4
  8            1-2-4-8            3
  9            1-2-4-6-9         16
  10           1-10               3

The tree of these paths is marked with green lines in the picture above.

Input data will contain three numbers N - the number of nodes, X0 - seed for random generator and S the index of starting vertex (from where we are to search for paths to others).
Answer should contain the route length to each vertex in the graph.

Example:

input data:
10 0 1

answer:
0 1 2 2 5 9 4 3 16 3

Attention: the length of the answer will be several kilobytes long - not very much, so it would give you no problem when copying and pasting it - but take care not to truncate it accidentally.