Dijkstra - Classic Problems | Repovive

CLS13. Dijkstra

1s256 MB

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

All edge weights are non-negative. If a vertex is unreachable from vertex $1$ , output $-1$ for that vertex.

\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 = \begin{cases} \text{shortest distance from } 1 \text{ to } i & \text{if reachable} \\ -1 & \text{otherwise} \end{cases}

Input

Explanation

For this input, the required output is 0 1 3 4.

Output

0 1 3 4

Input

3 2
1 2 10
2 3 20

Explanation

For this input, the required output is 0 10 30.

Output

0 10 30

Input

3 1
1 2 5

Explanation

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

Output

0 5 -1

1s256 MB

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

All edge weights are non-negative. If a vertex is unreachable from vertex $1$ , output $-1$ for that vertex.

\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 = \begin{cases} \text{shortest distance from } 1 \text{ to } i & \text{if reachable} \\ -1 & \text{otherwise} \end{cases}

Input

Explanation

For this input, the required output is 0 1 3 4.

Output

0 1 3 4

Input

3 2
1 2 10
2 3 20

Explanation

For this input, the required output is 0 10 30.

Output

0 10 30

Input

3 1
1 2 5

Explanation

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

Output

0 5 -1