Bellman-Ford (BF) - Classic Problems | Repovive

CLS15. Bellman-Ford (BF)

1s256 MB

Given a weighted directed graph with $n$ vertices and $m$ edges, find the shortest distance from vertex $1$ to all other vertices.

Edge weights can be negative. If a vertex is unreachable, output INF. If a vertex is affected by a negative cycle (distance can be $-\infty$ ), output -INF.

Constraints

$1 \le n \le 1000$
$0 \le m \le 5000$
$-10^6 \le w_i \le 10^6$ (edge weights)

Input

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_m \quad v_m \quad w_m \end{array}

Output

d_1 \quad d_2 \quad \cdots \quad d_n

d_i \in \{\text{shortest distance}, \texttt{INF}, \texttt{-INF}\}

Samples

Input

Explanation

For this input, the required output is 0 1 -1 0.

Output

0 1 -1 0

Input

Explanation

For this input, the required output is 0 -INF -INF.

Output

0 -INF -INF

Input

4 2
1 2 5
3 4 3

Explanation

For this input, the required output is 0 5 INF INF.

Output

0 5 INF INF

Given a weighted directed graph with $n$ vertices and $m$ edges, find the shortest distance from vertex $1$ to all other vertices.

Edge weights can be negative. If a vertex is unreachable, output INF. If a vertex is affected by a negative cycle (distance can be $-\infty$ ), output -INF.

$1 \le n \le 1000$
$0 \le m \le 5000$
$-10^6 \le w_i \le 10^6$ (edge weights)

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_m \quad v_m \quad w_m \end{array}

d_1 \quad d_2 \quad \cdots \quad d_n

d_i \in \{\text{shortest distance}, \texttt{INF}, \texttt{-INF}\}