C. Разрыв отношений
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии снова непростые времена! Многие города имеют настолько напряжённые отношения, что возможна даже гражданская война.

Всего в Бердяндии n городов, некоторые пары из которых соединены двусторонними дорогами. Не гарантируется, что из любого города можно добраться до любого другого, используя данные дороги.

Города s и t заявили об окончательном разрыве каких-либо отношений и намереваются исключить возможность перемещения между ними по дорогам. Теперь, возможно, необходимо закрыть несколько дорог так, чтобы перемещение из s в t по дорогам стало невозможным. Каждый город согласен потратиться на закрытие не более чем одной дороги, следовательно, суммарно закрытых дорог должно быть не более двух.

Помогите найти такой набор из не более чем двух дорог, что после закрытия данных дорог не будет существовать пути между s и t. Для каждой дороги оценён бюджет на её закрытие. Среди всех наборов найдите такой, что суммарный бюджет на закрытие всех дорог набора минимален.

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

В первой строке входных данных записаны два числа n и m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 30 000) — количество городов в Берляндии и количество дорог соответственно.

Во второй строке записаны целые числа s и t (1 ≤ s, t ≤ n, s ≠ t) — номера разрывающих отношения городов.

Далее следуют m строк, каждая из которых содержит три целых числа xi, yi и wi (1 ≤ xi, yi ≤ n, 1 ≤ wi ≤ 109) — номера городов, которые соединяет i-я дорога, и бюджет на её закрытие.

Все дороги двусторонние. Допускается, что пара городов соединена более чем одной дорогой. Допустимы дороги, которые соединяют город с самим собой.

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

В первую строку выведите минимальный бюджет на разрыв отношений между s и t, если разрешено закрыть не более двух дорог.

Во вторую строку выведите значение c (0 ≤ c ≤ 2) — количество дорог, которые необходимо закрыть в найденном решении.

В третью строку выведите в произвольном порядке c различных целых чисел от 1 до m — индексы закрываемых дорог. Считайте, что дороги пронумерованы от 1 до m в порядке их записи во входных данных.

Если ответа не существует, то есть невозможно сделать города s и t несвязными, удалив не более двух дорог, то выходные данные должны содержать единственную строку со значением -1.

Если оптимальных решений несколько, то выведите любое из них.

Примеры
Входные данные
6 7
1 6
2 1 6
2 3 5
3 4 9
4 6 4
4 6 5
4 5 1
3 1 3
Выходные данные
8
2
2 7
Входные данные
6 7
1 6
2 3 1
1 2 2
1 3 3
4 5 4
3 6 5
4 6 6
1 5 7
Выходные данные
9
2
4 5
Входные данные
5 4
1 5
2 1 3
3 2 1
3 4 4
4 5 2
Выходные данные
1
1
2
Входные данные
2 3
1 2
1 2 734458840
1 2 817380027
1 2 304764803
Выходные данные
-1