Вас наняли для постройки системы транспортировки воды между двумя точками в старом здании завода, используя существующие детали старой сантехники. Старые детали состоят из труб и соединений. Соединениями являются точки, где возможно ранее соединялись трубы. Мы говорим \textbf{ранее} соединялись, потому что некоторые из старых труб были повреждены и уничтожены, фактически оставив открытыми отверстия в соединениях, к которым они были подключены. Если вода попадет в одно из этих соединений, то она выйдет наружу и в конечном итоге затопит здание, что явно нежелательно. Вы можете исправить эту ситуацию путем установки новых труб между открытыми отверстиями или установки заглушек, закупоривающих открытые отверстия. После установки новой трубы, соединяющей два отверстия (которые должны принадлежать двум разным соединениям), эти отверстия уже не являются открытыми и вода может пройти через новую трубу. Стоимость установки новой трубы равна расстоянию между центрами двух соединений, которые эта труба соединяет. Стоимость установки заглушки в открытое отверстие равно \textbf{0.5}. Вам не следует беспокоиться об открытых отверстиях в местах соединения, куда никогда не доберется вода. Два соединения являются специальными. Одно называется \textit{источником} - точкой, через которую вода поступает в систему. Второе называется \textit{стоком} - точкой, в которую должна поступать вода. После установки новых труб и заглушек вода будет закачиваться насосами в исток под давлением, достаточным для поднятия воды до некоторой определенной высоты (если при этом конечно же отсутствует течь). Вы можете произвольным образом выбрать давление и не изменять его во время работы системы. Естественно, давления должно быть достаточно, чтобы поднять воду до высоты источника и стока. Ваша задача состоит в том, чтобы найти самый дешевый способ доставки воды из источника к стоку, не затопив при этом само здание. Рисунок ниже соответствует первому тесту, где черные точки соответствуют открытым отверстиям, соединение \textbf{1} является источником, а соединение \textbf{7} стоком (положения черных точек на окружностях не имеют значения, и используются только для илюстрации). \includegraphics{https://static.e-olymp.com/content/8e/8e651b61997a9630c1b964e29c992f7032bf61b8.jpg} Вода течет в системе по законам физики. Если давления достаточно для заполнения соединения, то соединение остается заполненным водой. Если из соединения с водой исходят горизонтальные трубы или трубы, идущие вниз, то вода потечет по этим трубам. Вода также может течь по трубам вверх в зависимости от имеющегося давления. Если вода достигнет открытого отверстия в соединении, то она затопит здание. В первом тесте Вам следует соединить узлы \textbf{1} и \textbf{5} стоимостью \textbf{3}, закупорить отверстия в соединении \textbf{2}, и установить давление таким образом, чтобы поднять воду только до соединения \textbf{7}. Вода заполнит соединения \textbf{1}, \textbf{2}, \textbf{5}, \textbf{6}, \textbf{7} и не поднимется выше. Другое (более дорогое) решение состоит в том чтобы закупорить все отверстия за цену \textbf{5}, и позволить воде течь по всем соединениям. Задачу нельзя решить соединением трубой узлов \textbf{1} и \textbf{6} и закупориванием отверстий в соединениях \textbf{2} и \textbf{5}, поскольку соединение \textbf{6} не имеет открытых отверстий, в которые можно было бы вставить трубу. Считайте, что существующие трубы и любые новые не мешают друг другу и не пересекаются с соединениями, кроме тех, к которым они подключены. То есть даже если прямая линия, соединяющая соединения \textbf{A} и \textbf{B} проходит через \textbf{C}, любая труба от \textbf{A} к \textbf{B} не касается \textbf{C}. \InputFile Первая строка каждого теста содержит два целых числа \textbf{N} и \textbf{M}, где \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{400}) - количество соединений в здании (пронумерованных с \textbf{1} до \textbf{N}), а \textbf{M} (\textbf{0} ≤ \textbf{M} ≤ \textbf{50000}) - количество существующих труб, пригодных для использования. Каждая из следующих \textbf{N} строк содержит четыре целых числа \textbf{x_i}, \textbf{y_i}, \textbf{z_i} и \textbf{k_i}, удовлетворяющих условиям: \textbf{-10000} ≤ \textbf{x_i}, \textbf{y_i}, \textbf{z_i} ≤ \textbf{10000} и \textbf{0} ≤ \textbf{k_i} ≤ \textbf{400}, \textbf{i} = \textbf{1}, \textbf{2}, ..., \textbf{N}. \textbf{i}-ая строка описывает соединение \textbf{i}: (\textbf{x_i}, \textbf{y_i}, \textbf{z_i}) - месторасположение \textbf{i}-го соединения, где ось \textbf{Оz} расположена вертикально; \textbf{k_i} указывает на количество открытых отверстий в соединении. Каждая из следующих \textbf{M} строк содержит два целых числа \textbf{a_j} и \textbf{b_j} (\textbf{1} ≤ \textbf{a_j} < \textbf{b_j} ≤ \textbf{N}). \textbf{j}-ая строка указывает на то, что \textbf{j}-ая труба соединяет узлы \textbf{a_j} и \textbf{b_j}. Между любой парой соединений может находиться не более одной трубы, никакие два соединения не имеют одинаковых координат. Источником является соединение \textbf{1}, а стоком соединение \textbf{N}. \OutputFile Для каждого теста следует вывести его номер. Если требуемую систему труб и заглушек можно сконструировать, то следует вывести наименьшую стоимость, за которую можно соединить источник со стоком в точности с четырьмя десятичными знаками. Если искомой сети соединений не существует, то вывести слово \textbf{impossible}.