The Shortest Path#4856

The Shortest Path

2 seconds

128 megabytes

Medium

Given an undirected weighted graph, find the shortest path between two specified vertices.

\InputFileThe first line contains two positive integers $n$ and $m$ ( $n \leq 2000$ n \leq 2000, $m \leq 50000$ m \leq 50000) — the number of vertices and edges in the graph.

The second line contains two integers $s$ and $f$ ( $1 \leq s, f \leq n$ 1 \leq s, f \leq n, $s \neq = f$ s \neq f) — the numbers of the start and end vertices between which you must find the shortest path.

Each of the next $m$ lines contains three integers $b_{i}$ b_i, $e_{i}$ e_i, and $w_{i}$ w_i ( $1 \leq b_{i}, e_{i} \leq n$ 1 \leq b_i, e_i \leq n, $0 \leq w_{i} \leq 1 0^{5}$ 0 \leq w_i \leq 10^5) — the endpoints and weight of the $i$ -th edge.

\OutputFileOn the first line, print one integer — the length of the shortest path between vertices $s$ and $f$ .

On the second line, print all the vertices on the shortest path from $s$ to $f$ in order, separated by spaces.

If there is no path from $s$ to $f$ , print -1.

Examples

Example 1

Loading

n \leq 2000

m \leq 50000

1 \leq s, f \leq n

s \neq = f

b_{i}

e_{i}

w_{i}

1 \leq b_{i}, e_{i} \leq n

0 \leq w_{i} \leq 1 0^{5}