Problem

Figure 1. The graph from the dataset

The task is to use Bellman-Ford algorithm to compute single-source shortest distances in a directed graph with possibly negative edge weights (but without negative cycles).

Given: A simple directed graph with integer edge weights from $-10^{3}$ to $10^3$ and $n \le 10^3$ vertices in the edge list format.

Return: An array $D[1..n]$ where $D[i]$ is the length of a shortest path from the vertex $1$ to the vertex $i$ ($D[1]=0$). If $i$ is not reachable from $1$ set $D[i]$ to x.

See Figure 1 for visual example from the sample dataset.

Sample Dataset

9 13
1 2 10
3 2 1
3 4 1
4 5 3
5 6 -1
7 6 -1
8 7 1
1 8 8
7 2 -4
2 6 2
6 3 -2
9 5 -10
9 4 7

Sample Output

0 5 5 6 9 7 9 8 x