В одній феодальній державі середньовічної Європи було \(n\) міст і \(m\) доріг, кожна з яких поєднувала деякі два міста. Кожна дорога належала правителю одного з міст (не обов'язково одного з тих, що вона з'єднувала). Якось правитель міста \(S\) вирішив оголосити війну правителю міста \(T\). Перед ним відразу ж постало нелегке завдання: як довести армію до міста \(T\).

Правитель кожного міста вимагає плату за прохід військ через його місто. Крім того, правитель міста \(S\) може переміщати війська лише дорогами, що належать йому. При цьому він може купити будь-яку дорогу у її власника за певну плату (навіть якщо власник – правитель міста T). На жаль, усі гроші зі скарбниці міста \(S\) були витрачені на попередній невдалий військовий похід, тому спочатку правителю доведеться продати деякі свої дороги (зрозуміло, після цього він не зможе провести по них війська).

Допоможіть правителю з'ясувати, які дороги слід продати, а які купити, щоб довести війська від міста \(S\) до міста \(T\) і оплатити прохід через усі проміжні міста. Усі операції продажу та купівлі доріг треба здійснити до початку походу, поки правителі інших міст не здогадалися про войовничі наміри правителя міста \(S\).

Формат вхідних даних

В першому рядку вводяться цілі числа \(n\) і \(m\) – кількість міст і доріг відповідно ( \(2 \le n \le 2000\), \(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\)).

Далі йдуть рядки, що задають описи доріг. Дорога описується чотирма цілими числами: \(a_i, b_i, p_i\) та \(c_i\). Тут \(a_i\) та \(b_i\) – номери міст, які з'єднує дорога, \(p_i\) – номер міста, правителю якого вона належить, \(c_i\) – її вартість (\( a_i \neq b_i\), \(1 \le c_i \le 10 000\)). По дорозі можна переміщатися в обох напрямках. Будь-які два міста з'єднані не більше, ніж однією дорогою.

Формат вихідних даних

У першому рядку виведіть список доріг, які потрібно продати у наступному форматі: спочатку кількість доріг, а потім їх номери. Дороги нумеруються з одиниці у тому порядку, в якому вони задані у вхідних даних.

У другому рядку виведіть список доріг, які потрібно купити, у тому ж форматі.

У третьому рядку виведіть маршрут походу – номери міст у порядку проходження війська. Якщо рішень кілька, виведіть будь-яке.

Якщо рішення немає, виведіть число -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