В одном феодальном государстве средневековой Европы было \(n\) городов и \(m\) дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно одного из тех, которые она соединяла). Однажды правитель города S решил объявить войну правителю города T. Перед ним сразу же встала нелегкая задача: как довести армию до города T.
Правитель каждого города требует плату за проход войск через его город. Кроме того, правитель города S может перемещать войска только по дорогам, которые принадлежат ему. При этом он может купить любую дорогу у ее владельца за определенную плату (даже если владелец — правитель города T). К сожалению, все деньги из казны города S были потрачены на предыдущий неудачный военный поход, поэтому сначала правителю придется продать некоторые свои дороги (разумеется, после этого он не сможет провести по ним войска).
Помогите правителю выяснить, какие дороги следует продать, а какие купить, чтобы довести войска от города S до города T и оплатить проход через все промежуточные города. Все операции продажи и покупки дорог надо осуществить до начала похода, пока правители других городов не догадались о воинственных намерениях правителя города S.
Формат входных данных
Первая строка содержит целые числа \(n\) и \(m\) — количество городов и дорог соответственно (\(2 \le n \le 2\,000\), \(1 \le m \le 50\,000\)). Города нумеруются от 1 до \(n\), города S и T имеют номера 1 и \(n\) соответственно.
Следующие \(n\) строк содержат под одному целому числу \(r_i\) — плату за проезд через город \(i\) (\(0 \le r_i \le 10\,000\), \(r_1 = r_n = 0\)).
Следующие \(m\) строк содержат описания дорог. Дорога описывается четырьмя целыми числами: \(a_i\), \(b_i\), \(p_i\) и \(c_i\). Здесь \(a_i\) и \(b_i\) — номера городов, которые соединяет дорога, \(p_i\) — номер города, правителю которого она принадлежит, \(c_i\) — ее стоимость (\(a_i \ne b_i\), \(1 \le c_i \le 10\,000\)). По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более чем одной дорогой.
Формат выходных данных
На первой строке выведите список дорог, которые нужно продать в следующем формате: сначала число дорог, а затем их номера. Дороги нумеруются с единицы в том порядке, в котором они заданы во входных данных. На второй строке выведите список дорог, которые нужно купить, в том же формате. На третьей строке выведите маршрут похода — номера городов в порядке следования войска. Если решений несколько, выведите любое.
Если решения нет, выведите в выходной файл число \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
0
1
0
1 2 1 10
2 3 1 10
3 1 2 2
|
2 1 2
1 3
1 3
|