По дороге в школу Петя любит забегать в киоск и покупать себе мороженое. Однако при этом он часто опаздывает в школу. Неожиданно Петя понял - он просто ходит не по кратчайшему пути!
Помогите Пете победить опоздания. Город можно представить как 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
4).
Выходные данные
Если путь из дома Пети до школы, проходящий через перекресток с мороженым и не проходящий по одному перекрестку два раза, существует, выведите на первой строке выходного файла два целых числа K и L - количество улиц, которые проходит Петя в оптимальном пути и длину пути. На второй строке выведите номера перекрестков в том порядке, в котором их посещает Петя.
В противном случае выведите -1 на первой строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
1 5 3
1 2 1
2 3 4
2 4 1
3 4 2
1 5 1
4 5 2
|
4 9
1 2 3 4 5
|