Змішані плани польотів
Ad Hoc Поштова Компанія (AHPC) використовує просту стратегію доставки поштових конвертів: вона залучає волонтера, купує для нього найдешевший авіаквиток з початкового до кінцевого міста і передає йому сумку з конвертами в аеропорту відправлення, щоб він передав її кореспонденту компанії в аеропорту призначення.
Окрім прямих рейсів між двома аеропортами, існують непрямі маршрути з зупинками в кількох проміжних аеропортах. Пасажир непрямого маршруту завжди починає з першого аеропорту і відвідує проміжні аеропорти послідовно (згідно з розкладом непрямого маршруту, без використання інших прямих рейсів або непрямих маршрутів посередині), але може завершити маршрут в будь-якому проміжному аеропорту. Вартість непрямого маршруту фіксована; незалежно від того, чи пасажир використовує всі рейси або перериває маршрут посередині. План польоту може включати кілька прямих рейсів і повних або часткових непрямих маршрутів.
З метою економії, AHPC прагне використовувати комбіновані плани польотів: припустимо, що є пара сумок, одну потрібно доставити з A до B, а іншу з C до D (A, B, C, D — різні аеропорти). Компанія може купити два плани польотів з A до D для першого волонтера і з C до B для другого, так що обидва плани мають спільний аеропорт M (не обов'язково відмінний від цих 4 аеропортів), де волонтери зустрічаються і обмінюються сумками. Таким чином, AHPC гарантує, що кожна сумка доставлена до правильного місця призначення, при цьому загальна вартість може бути знижена.
Як приклад, шість аеропортів разом з прямими рейсами (суцільні стрілки), непрямими маршрутами (штрихові та крапкові стрілки) і їхніми цінами показані на наведеній вище схемі. Дві сумки повинні бути відправлені, одна з аеропорту 3 (A) до 5 (B), інша з 6 (C) до 1 (D). Компанія може придбати (3, 4), (4, 5) як план польоту для першого волонтера, і (6, 5), (5, 1) для другого із загальною вартістю 300. Але дешевшою альтернативою буде (3, 4, 1, 2, 6) для першого і (6, 2), (2, 4, 5) для другого волонтера, із загальною вартістю 250. Волонтери зустрічаються і обмінюються сумками в аеропорту 4 (M), а перший волонтер залишить непрямий маршрут в аеропорту 1.
Вам потрібно написати програму, яка, отримавши інформацію про рейси, знаходить найбільш економічну вартість доставки сумок.
Вхідні дані
У вхідних даних кілька випадків. Перша строка кожного випадку містить шість цілих чисел n, m, A, B, C і D, де n (4 ≤ n ≤ 100) — кількість аеропортів, а m (0 ≤ m ≤ 10000) — загальна кількість прямих рейсів і непрямих маршрутів, де не більше 1000 з них є непрямими маршрутами. i-й рядок з наступних m рядків починається з двох додатних цілих чисел p_i (ціна, p_i ≤ 10^6) і s_i (дорівнює 1 для прямого рейсу і більше для непрямого маршруту), за якими слідують s_i+1 різних номерів аеропортів, що показують порядок аеропортів, які відвідуються в i-му прямому рейсі/непрямому маршруті.
Вхідні дані завершуються рядком "0 0 0 0 0 0", який не слід обробляти.
Вихідні дані
Для кожного тестового випадку виведіть загальну вартість найдешевшого плану польоту в рядку, або виведіть "Impossible!" (без лапок), якщо доставка хоча б однієї сумки неможлива.