오래된 공장의 급수 배관

당신은 오래된 공장에서 두 지점 사이로 물을 보내는 시스템을, 건물에 남아 있는 낡은 배관을 재활용하여 만들기로 했다. 낡은 배관은 파이프와 접합점(junction)으로 이루어져 있다. 접합점은 예전에 파이프들이 연결되어 있던 지점이다. 일부 낡은 파이프는 손상되어 제거되었고, 그 결과 그 파이프가 연결되어 있던 접합점에는 열린 구멍이 남았다. 물이 열린 구멍에 닿으면 그 구멍으로 물이 쏟아져 건물이 침수되므로, 이런 일은 반드시 피해야 한다.

이 문제는 열린 구멍 사이에 새 파이프를 설치하거나, 열린 구멍을 마개로 막아서 해결할 수 있다. 새 파이프는 서로 다른 두 접합점에 있는 두 개의 열린 구멍을 잇는다. 파이프를 설치하면 그 두 구멍은 막히고, 물은 그 파이프를 통해 흐를 수 있다. 새 파이프의 비용은 두 접합점 중심 사이의 유클리드 거리와 같다. 마개 하나의 비용은 $0.5$이다. 물이 절대 닿지 않는 접합점의 열린 구멍은 신경 쓰지 않아도 된다.

두 접합점은 특별하다. 하나는 물을 밀어 넣는 출발점(접합점 $1$)이고, 다른 하나는 물이 필요한 도착점(접합점 $N$)이다. 마개와 새 파이프를 모두 설치한 뒤, 물은 출발점에서 당신이 정한 높이까지 올라갈 수 있는 압력으로 주입된다. 압력은 일정하며 자유롭게 정할 수 있지만, 적어도 출발점과 도착점의 높이까지 물을 밀어 올릴 수 있을 만큼은 되어야 한다. 목표는 건물을 침수시키지 않으면서 출발점에서 도착점까지 물을 보내는 가장 저렴한 방법을 찾는 것이다.

물은 다음 규칙을 따른다. 압력이 어떤 접합점을 채울 만큼 충분하면 그 접합점은 물로 찬 상태를 유지한다. 물이 찬 접합점에서, 물은 수평이거나 아래로 향하는 파이프로는 언제나 흐르고, 위로 향하는 파이프로는 압력이 정한 높이까지만 흐른다. 즉, 당신이 정한 수위를 $H$라 하면, 물은 높이가 $H$ 이하인 접합점들 중에서, 높이가 $H$ 이하인 접합점만을 지나는 파이프 경로로 출발점과 연결된 접합점들을 정확히 채운다. 물이 찬 접합점의 열린 구멍에 물이 닿으면 건물이 침수된다.

기존 파이프와 새 파이프는 서로, 그리고 자신이 연결하는 접합점 이외의 다른 접합점과 절대 간섭하지 않는다(두 접합점을 잇는 선분이 세 번째 접합점을 지나더라도 닿지 않는다).

입력은 여러 개의 테스트 케이스로 이루어져 있으며 파일의 끝에서 종료된다.

각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $M$이 주어진다. $N$ ($2 \le N \le 400$)은 접합점의 수이고(접합점은 $1$번부터 $N$번까지 번호가 매겨진다), $M$ ($0 \le M \le 50000$)은 사용 가능한 기존 파이프의 수이다.

이어지는 $N$개의 줄에는 각각 네 정수 $x_i$, $y_i$, $z_i$, $k_i$가 주어지며, $-10000 \le x_i, y_i, z_i \le 10000$, $0 \le k_i \le 400$을 만족한다. $i$번째 줄은 접합점 $i$를 나타낸다. $(x_i, y_i, z_i)$는 그 위치이고 $z$축이 수직 방향이며, $k_i$는 그 접합점에 있는 열린 구멍의 수이다.

이어지는 $M$개의 줄에는 각각 두 정수 $a_j$와 $b_j$가 주어지며 $1 \le a_j < b_j \le N$을 만족한다. 이는 파이프 $j$가 접합점 $a_j$와 $b_j$를 잇는다는 뜻이다. 어떤 두 접합점을 잇는 파이프는 많아야 하나이고, 좌표가 같은 두 접합점은 없다. 출발점은 접합점 $1$, 도착점은 접합점 $N$이다.

각 테스트 케이스마다 한 줄에 Case x: v 형식으로 출력한다. x는 $1$부터 시작하는 테스트 케이스 번호이다. 건물을 침수시키지 않고 출발점과 도착점을 연결할 수 있으면 v는 최소 총비용을 소수점 아래 넷째 자리까지 정확히 출력한 값이고, 불가능하면 v는 impossible이라는 단어이다.