An edge-weighted graph G (V, E) and the source r.

$|V|\ |E|\ r$

$s_0\ t_0\ d_0$

$s_1\ t_1\ d_1$

$:$

$s_{|E|−1}\ t_{|E|−1}\ d_{|E|−1}$

$|V|$ is the number of vertices and $|E|$ is the number of edges in $G$. The graph vertices are named with the numbers $0, 1,..., |V|−1$ respectively. r is the source of the graph.

$s_i$ and $t_i$ represent source and target vertices of $i$-th edge (directed) and $d_i$ represents the cost of the $i$-th edge.

If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value) which is reachable from the source $r$, print

NEGATIVE CYCLE

Otherwise, print

$c_0$

$c_1$

$:$

$c_{|V|−1}$

The output consists of $|V|$ lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|−1 in order. If there is no path from the source to a vertex, print "INF".