# ADA Training CP

# The Shortest Path

The undirected weighted graph is given. Find the shortest path between two given vertices.

## Input data

The first line contains two positive integers n and m (n ≤ 2000, m ≤ 50000) - the number of vertices and edges in a graph. The second line contains positive integers s and f (1 ≤ s, f ≤ n, s ≠ f) - the numbers of the vertices, the minimal length between which must be found. Each of the next m lines contains three numbers `b[i]`

, `e[i]`

and `w[i]`

- the numbers of the ends of i-th edge and its weight correspondingly (1 ≤ `b[i]`

, `e[i]`

≤ n, 0 ≤ `w[i]`

≤ `10^5`

).

## Output data

Print in the first line one number - the length of minimal path between the vertices s and f. Print in the second line all the vertices on the shortest path from s to f in the traversal order. If the path from s to f does not exist, print -1.

## Examples

4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4

3 1 2 3