Ice cream

On his way to school, Petya enjoys stopping by a kiosk to buy ice cream. However, this often makes him late for school. Petya suddenly realized that he isn't taking the shortest route!

Help Petya avoid being late. The city is represented as n intersections connected by m streets, each with a known length. Petya's house is at intersection a, the school is at intersection b, and the ice cream kiosk is at intersection c. On his journey to school, Petya never visits the same intersection more than once.

Input

The first line of the input contains the numbers n and m (3 ≤ n ≤ 30000, 0 ≤ m ≤ 50000). The second line contains three distinct numbers: a, b, and c. The next m lines each contain three integers x_i, y_i, and l_i, representing the intersections connected by a street and its length (with length being a positive integer not exceeding 10^4).

Output

If there is a path from Petya's house to the school that passes through the ice cream intersection without revisiting any intersection, output two integers k and l on the first line: the number of streets Petya takes on the optimal path and the total length of the path. On the second line, list the intersections in the order Petya visits them. If no such path exists, output -1 on the first line.