Задача: Мороженое

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

Помогите Пете победить опоздания. Город можно представить как N перекрестков, соединенных M улицами, про каждую улицу известна ее длина. Дом Пети находится на перекрестке A, школа - на перекрестке B, а киоск с мороженым - на перекрестке C. По пути в школу Петя никогда не проходит через один перекресток дважды.

Входные данные

Первая строка содержит числа N и M (3 ≤ N ≤ 30 000, 0 ≤ M ≤ 50 000). Вторая строка содержит три различных числа - A, B и C. Следующие M строк содержат по три целых числа X_i, Y_i и L_i - номера перекрестков, соединенных улицей и ее длину (длина - целое положительное число, которое не превышает 10⁴).

Выходные данные

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

В противном случае выведите -1 на первой строке.

Ваш ответ: