레이팅 미적용당신은 오래된 공장 건물에서 기존 배관 부품 일부를 이용해 두 지점 사이에 물을 수송하는 시스템을 만드는 일을 맡았다. 기존 부품은 파이프와 접합부로 이루어져 있다. 접합부는 예전에 파이프들이 연결되어 있었을 수 있는 지점이다. “예전에 연결되어 있었다”라고 말하는 이유는, 오래된 파이프 중 일부가 손상되어 제거되면서 그 파이프가 연결되어 있던 접합부에 사실상 뚫린 구멍이 남았기 때문이다. 물이 이런 접합부에 들어가면 뚫린 구멍으로 쏟아져 나와 결국 건물이 물에 잠기게 된다. 이는 분명 바람직하지 않은 일이다. 이 상황은 뚫린 구멍들 사이에 새 파이프를 설치하고, 필요에 따라 다른 뚫린 구멍을 마개로 막아 해결할 수 있다. 두 구멍(서로 다른 두 접합부에 있어야 한다)을 연결하는 새 파이프를 설치하면 두 구멍은 더 이상 뚫려 있지 않게 되고, 물이 새 파이프를 통해 흐를 수 있다. 새 파이프 설치 비용은 파이프가 연결하는 두 접합부 중심 사이의 거리와 같다. 뚫린 구멍 하나에 마개를 설치하는 비용은 0.5이다. 물이 결코 도달하지 않을 접합부의 뚫린 구멍은 신경 쓰지 않아도 된다. 접합부 중 두 개는 특별하다. 하나는 수원(source)이라 불리며 새 시스템에 물이 펌프로 주입되는 지점이다. 다른 하나는 목적지(destination)라 불리며 물이 필요한 곳이다. 마개와 새 파이프를 시스템에 추가한 뒤, 수원에서 특정 높이까지 도달하기에 충분한 압력으로 물이 주입된다(물론 누수가 없다는 가정하에). 압력은 임의로 선택할 수 있으며, 시스템 가동 중에 압력이 변하지 않음이 보장된다. 당연히 압력은 물을 수원과 목적지 두 곳의 높이까지 밀어 올리기에 충분해야 한다. 당신의 임무는 건물을 물에 잠기게 하지 않으면서 수원 접합부에서 목적지 접합부까지 물을 보내는 가장 저렴한 방법을 찾는 것이다. 아래 그림은 첫 번째 샘플 입력에 해당하며, 검은 점은 뚫린 구멍을 나타내고 접합부 1이 수원, 접합부 7이 목적지이다. (원 위에서 검은 점의 위치는 의미가 없으며 단지 그림 표현을 위한 것이다.) 물은 물리 법칙에 따라 시스템을 흐른다. 압력이 어떤 접합부를 물로 채우기에 충분하면 그 접합부는 물로 가득 찬 상태를 유지한다. 접합부에서 수평 또는 아래 방향으로 뻗은 파이프가 있으면 물은 그 파이프로도 흐른다. 물은 또한 수압이 정하는 높이까지 접합부에 연결된 파이프를 타고 위로도 흐른다. 물론 물이 접합부의 뚫린 구멍에 도달하면 구멍으로 흘러나와 건물이 물에 잠긴다. 첫 번째 샘플 입력에서는 비용 3으로 접합부 1과 5를 연결하고, 접합부 2의 뚫린 구멍들을 막고, 물이 접합부 7까지만 올라가도록 압력을 설정할 수 있다. 물은 접합부 1, 2, 5, 6, 7을 채우고 더 높이 흐르지 않는다. 다른(더 비싼) 해법은 총비용 5로 모든 구멍을 막고 물이 모든 접합부를 흐르게 하는 것이다. 접합부 1과 6을 연결하고 접합부 2와 5의 구멍을 막는 방법으로는 이 케이스를 풀 수 없는데, 접합부 6에는 새 파이프를 연결할 수 있는 뚫린 구멍이 없기 때문이다. 기존 파이프와 새 파이프는 자신이 연결된 접합부를 제외하면 서로 간에도, 어떤 접합부와도 간섭하지 않는다고 가정한다. 즉, 접합부 A에서 접합부 B로 가는 직선이 접합부 C를 지나더라도 A에서 B로 가는 파이프는 C에 닿지 않는다.
각 테스트 케이스의 첫 줄에는 두 정수 \(N\)과 \(M\)이 주어진다. \(N\) (\(2 \le N \le 400\))은 건물의 접합부 수(1부터 \(N\)까지 번호가 매겨짐)이고 \(M\) (\(0 \le M \le 50\,000\))은 사용할 수 있는 기존 파이프의 수이다. 다음 \(N\)개의 줄에는 각각 네 정수 \(xi\), \(yi\), \(zi\), \(ki\)가 주어지며, satisfyi\(ng - 10\,000 \le xi\), y\(i\), z\(i \le 10\,000\), \(0 \le ki \le 400\), \(i = 1\), 2, ..., N을 만족한다. \(i^{th}\)번째 줄은 접합부 \(i\)를 설명한다. (\(x_{i}\), y_{i}, z_{i})는 \(i^{th}\)번째 접합부의 위치이고 여기서 \(z-ax\)is가 수직축이다. \(k_{i}\)는 그 접합부의 뚫린 구멍 수를 나타낸다. 다음 \(M\)개의 줄에는 각각 \(1 \le aj < bj \le N\)을 만족하는 두 정수 \(a_{j}\)와 \(b_{j}\)가 주어진다. \(j^{th}\)번째 줄은 파이프 \(j\)가 접합부 \(aj\)와 \(bj\)를 연결함을 나타낸다. 어떤 접합부 쌍도 최대 하나의 파이프로 연결되며, 좌표가 같은 두 접합부는 없다. 수원은 접합부 1이고 목적지는 접합부 \(N\)이다.
각 케이스마다 케이스 번호를 출력한다. 그런 다음 적절한 새 파이프와 마개로 원하는 시스템을 만들 수 있으면 수원 접합부와 목적지 접합부를 연결하는 최소 비용을 소수점 아래 넷째 자리까지 정확하게 출력한다. 수원과 목적지를 연결할 수 없으면 impossible을 출력한다.
7 6
2 0 1 1
0 0 0 2
1 0 4 3
3 0 4 3
5 0 1 1
3 0 2 0
5 0 3 0
1 2
1 3
3 4
4 7
5 7
6 7
4 1
2 0 0 0
3 0 1 0
4 1 0 1
5 1 1 1
1 2
Case 1: 4.0000
Case 2: impossible