Алгоритм Форда-Фалкерсона

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

Помогите Пете победить опоздания. Город можно представить как 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 на первой строке.

Рассмотрим таблицу размера MxN, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает R_i, и для всех j сумма чисел ее j-го столбца не превышает Cj.

Вам задана таблица Z размера MxN, в некоторых клетках которой уже стоят целые неотрицательные числа. Найдите симпатичную таблицу с максимальной суммой элементов такую, что она совпадает с Z на тех клетках, в которых в Z стоят числа.

Входные данные
Первая строка входных данных содержит числа M и N (1 <= M, N <= 20). Следующая строка содержит M целых неотрицательных чисел - R₁, R₂, ..., R_M. Далее идет строка, содержащая N целых неотрицательных чисел C₁, C₂, ..., C_N. Все вводимые ограничения не превышают 106. Следующие M строк содержит по N целых чисел, которые задают Z. Если на некотором месте в таблице Z отсутствует число, то на этом месте во входных данных стоит  -1.

Выходные данные
Выведите найденную таблицу – M строк по N чисел. Если решения не существует, выведите единственное число -1.
 

Примеры

№	Входные данные	Выходные данные
1	2 2 1 10 1 10 -1 -1 -1 1	0 1  1 1