Потік мінімальної вартості#3393
Вас найняли для створення системи транспортування води між двома точками в старій будівлі заводу, використовуючи наявні деталі старої сантехніки. Ці деталі складаються з труб і вузлів. Вузол — це точка, де раніше могли з'єднуватися труби. Ми говоримо раніше, тому що деякі старі труби були пошкоджені і знищені, залишивши відкритими отвори у вузлах, до яких вони були підключені. Якщо вода потрапить в один з таких вузлів, вона витече назовні і затопить будівлю, що, звісно, небажано.
Ви можете виправити цю ситуацію, встановивши нові труби між відкритими отворами або встановивши заглушки, щоб закрити відкриті отвори. Після встановлення нової труби, що з'єднує два отвори (які повинні належати різним вузлам), ці отвори більше не будуть відкритими, і вода може проходити через нову трубу. Вартість встановлення нової труби дорівнює відстані між центрами двох вузлів, які вона з'єднує. Вартість встановлення заглушки у відкритий отвір дорівнює . Вам не потрібно турбуватися про відкриті отвори у вузлах, куди вода ніколи не потрапить.
Два вузли є особливими. Один називається джерелом — це точка, через яку вода надходить у систему. Інший називається випуском — це точка, у яку вода має надходити. Після встановлення нових труб і заглушок вода закачуватиметься насосом у джерело під тиском, достатнім для підняття води до певної висоти (якщо, звісно, немає витоку). Ви можете вибирати тиск довільно і не змінювати його під час роботи системи. Природно, тиск має бути достатнім, щоб підняти воду до висоти джерела і випуску. Ваше завдання — знайти найдешевший спосіб доставки води з джерела до випуску, не затопивши при цьому будівлю.
Малюнок нижче відповідає першому тесту, де чорні точки — це відкриті отвори, вузол є джерелом, а вузол — випуском (положення чорних точок на колах не має значення і використовується лише для ілюстрації).
Вода тече в системі за законами фізики. Якщо тиск достатній для заповнення вузла, то вузол залишається наповненим водою. Якщо з вузла з водою виходять горизонтальні труби чи труби, що йдуть донизу, то вода потече цими трубами. Вода може також текти трубами вгору відповідно до наявного тиску. Якщо вода досягне відкритого отвору у вузлі, вона затопить будівлю.
У першому тесті слід з'єднати вузли і вартістю , встановити заглушки у відкриті отвори вузла і задати тиск так, щоб вода піднялась лише до вузла . Вода заповнить вузли , , , , і не підніметься вище. Інше (більш дороге) рішення полягає у встановленні заглушок у всі отвори за ціну і дозволі воді текти через усі вузли. Неможливо вирішити задачу, з'єднавши трубою вузли і й поставивши заглушки у вузлах і , оскільки у вузла немає відкритих отворів, куди можна було б під'єднати трубу.
Вважайте, що існуючі труби й усі нові не заважають одні одним і не перетинаються з вузлами, окрім тих, до яких вони підключені. Тобто навіть якщо пряма лінія, що з'єднує вузли і , проходить через , будь-яка труба від до не торкнеться .
Перший рядок кожного тесту містить два цілі числа і , де (2 \leq N \leq 400) — кількість вузлів у будівлі (пронумерованих з до ), а (0 \leq M \leq 50000) — кількість існуючих придатних для використання труб. Кожен з наступних рядків містить чотири цілі числа x_i, y_i, z_i і k_i такі, що -10000 \leq x_i, y_i, z_i \leq 10000 і 0 \leq k_i \leq 400, i = 1, 2, \ldots, N. -й рядок описує вузол : (x_i, y_i, z_i) — координати -го вузла, де вісь є вертикальною; k_i — кількість відкритих отворів у вузлі. Кожен з наступних рядків містить два цілі числа a_j і b_j (1 \leq a_j < b_j \leq N). -й рядок вказує, що -а труба з'єднує вузли a_j і b_j. Між будь-якою парою вузлів може бути не більше однієї труби, жодні два вузли не мають однакових координат. Джерелом є вузол , а випуском — вузол .
Для кожного тесту виведіть його номер. Якщо можливо побудувати потрібну систему труб і заглушок, то виведіть мінімальну вартість з'єднання джерела з випуском з точністю до чотирьох десяткових знаків. Якщо такої мережі не існує, виведіть слово impossible.
Приклад 1