Патруль шосе
Злочинність у місті Мегаполіс зростає. Щоб протидіяти злочинам, влада організувала патрулювання на автомагістралях. Місто складається з мережі односторонніх доріг. На кінцях кожної дороги розташовані базові станції для патрульних загонів. Кожна базова станція має певну кількість загонів. Спочатку кожна станція відправляє загін по всіх вихідних автомагістралях з цієї станції. Загін патрулює автомагістраль і, досягнувши станції на іншому кінці, чекає там, поки загін, що чекав найдовше, не відправиться по автомагістралі, яка не патрулювалася найдовше.
Незабаром виникли труднощі, оскільки частота патрулювання автомагістралей почала залежати від кількості доріг, що починаються і закінчуються на базовій станції. Якщо кількість доріг, що починаються на базовій станції, перевищує кількість тих, що закінчуються, дороги патрулюються рідше. І якщо жодна дорога не закінчується на певній базовій станції, то дороги, що починаються звідти, не будуть патрулюватися більше ніж один раз.
У цій ситуації патруль вирішив виключити деякі автомагістралі з розкладу патрулювання, щоб на кожній базовій станції кількість доріг, що починаються і закінчуються, була рівною. Решта автомагістралей буде контролюватися за допомогою відеоспостереження. Однак через певні питання безпеки є автомагістралі, які обов'язково повинні бути патрульовані.
Тепер, враховуючи вартість патрулювання автомагістралей і встановлення відеоспостереження, знайдіть мінімальну вартість моніторингу всього міста. Зверніть увагу, що відеоспостереження не може повністю замінити патруль. Тому має бути принаймні одна автомагістраль, яка буде патрульована.
Вхідні дані
Перший рядок вхідних даних містить ціле число T (T ≤ 70), кількість тестових випадків. Далі йдуть T тестових випадків. Кожен тестовий випадок починається з двох цілих чисел N (1 ≤ N ≤ 100) і M (1 ≤ M ≤ 1000), що представляють кількість базових станцій і автомагістралей відповідно. Далі йдуть M рядків, кожен з яких містить 5 цілих чисел: u, v, p, s, x (1 ≤ u, v ≤ N, 0 ≤ p, s ≤ 1000000). Тут u і v означають, що автомагістраль починається з базової станції u і закінчується на v, p — це вартість патрулювання, а s — це вартість встановлення відеоспостереження. Якщо автомагістраль повинна бути патрульована, то x дорівнює одиниці. В іншому випадку це нуль.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку, за яким слідує мінімальна вартість моніторингу автомагістралей. Якщо неможливо організувати патрулювання, задовольняючи задані обмеження, виведіть "impossible" (без лапок).