# ADA University - February 3 - Dijkstra

# The Shortest Path

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

#### Input

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`

and _{i}`w`

- the numbers of the ends of _{i}**i**-th edge and its weight correspondingly (**1** ≤ `b`

, _{i}`e`

≤ _{i}**n**, **0** ≤ `w`

≤ _{i}**100000**).

#### Output

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**.

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

3 1 2 3