eolymp
bolt
Try our new interface for solving problems
Problems

Мороженое

Мороженое

Time limit 1 second
Memory limit 64 MiB

По дороге в школу Петя любит забегать в киоск и покупать себе мороженое. Однако при этом он часто опаздывает в школу. Неожиданно Петя понял – он просто ходит не по кратчайшему пути!

Помогите Пете победить опоздания. Город можно представить как n перекрестков, соединенных m улицами, про каждую улицу известна ее длина. Дом Пети находится на перекрестке a, школа – на перекрестке b, а киоск с мороженым – на перекрестке c. По пути в школу Петя никогда не проходит через один перекресток дважды.

Input data

Первая строка входного файла содержит числа n и m (3n30000, 0m50000). Вторая строка содержит три различных числа – a, b и c. Следующие m строк содержат по три целых числа x_i, y_i и l_i – номера перекрестков, соединенных улицей и ее длину (длина – целое положительное число, которое не превышает 10^4).

Output data

Если путь из дома Пети до школы, проходящий через перекресток с мороженым и не проходящий по одному перекрестку два раза, существует, выведите на первой строке выходного файла два целых числа k и l – количество улиц, которые проходит Петя в оптимальном пути и длину пути. На второй строке выведите номера перекрестков в том порядке, в котором их посещает Петя. В противном случае выведите -1 на первой строке выходного файла.