你受雇于一家老旧工厂，需要利用现有的管道组件构建一个系统，以便在两个点之间输送水。旧的组件由管道（pipes）和接头（junctions）组成。接头是之前可能连接过管道的点。我们称之为“之前连接过”，是因为一些旧管道已经损坏并被移除，实际上在它们所连接的接头上留下了开口。如果水进入这些接头之一，它会从开口处流出并最终淹没建筑物——这显然是不希望发生的事件。

你可以通过在某些开口之间安装新管道，并根据需要安装塞子来封闭其他开口，从而补救这种情况。当你安装一根连接两个孔（必须位于两个不同的接头中）的新管道时，这两个孔就不再是开口，水将能够通过新管道流动。安装一根新管道的成本等于该管道所连接的两个接头中心之间的距离。在开口处安装塞子的成本为 $0.5$。你无需担心那些水永远无法到达的接头上的开口。

其中两个接头比较特殊。一个称为源点（source），是水被泵入新系统的点。另一个称为终点（destination），是需要用水的地方。在向系统添加任何塞子和新管道后，水将以足以到达指定高度的压力泵入源点（当然，是在没有泄漏的情况下）。你可以任意选择压力，并保证在系统运行期间压力不会改变。自然地，压力必须足以将水推送到源点和终点的高度。你的任务仅仅是找到一种最廉价的方法，将水从源接头输送到目标接头，且不淹没建筑物。

下图对应第一个样例输入，其中黑点代表开口，接头 $1$ 是源点，接头 $7$ 是终点。（黑点在圆圈上的位置没有意义，仅用于说明。）

水根据物理定律在系统中流动。如果压力足以使一个接头充满水，那么该接头将保持充满水的状态。如果从一个接头有水平或向下延伸的管道，那么水也会流过这些管道。水也会通过连接到接头的管道向上流动，直到达到由水压决定的高度。当然，如果水到达了接头上的一个开口，它就会流过该孔并淹没建筑物。

在第一个样例输入中，你可以连接接头 $1$ 和 $5$（成本为 $3$），堵住接头 $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$ 行，每行包含四个整数 $x_i, y_i, z_i$ 和 $k_i$，满足 $-10\,000 \le x_i, y_i, z_i \le 10\,000$ 且 $0 \le k_i \le 400$，$i = 1, 2, \dots, N$。第 $i$ 行描述接头 $i$：$(x_i, y_i, z_i)$ 是第 $i$ 个接头的位置，其中 $z$ 轴为垂直轴；$k_i$ 表示接头中开口的数量。接下来的 $M$ 行，每行包含两个整数 $a_j$ 和 $b_j$，满足 $1 \le a_j < b_j \le N$。第 $j$ 行表示管道 $j$ 连接接头 $a_j$ 和 $b_j$。任意一对接头之间最多连接一根管道，且没有两个接头共享相同的坐标。源点是接头 $1$，终点是接头 $N$。

输出格式

对于每个用例，显示用例编号。然后，如果可以使用合适的新管道和塞子来构建所需的系统，则显示将源接头连接到目标接头的最低成本，精确到小数点后四位。如果无法将源点连接到终点，则显示单词 impossible。

样例

样例输入 1

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

样例输出 1

Case 1: 4.0000
Case 2: impossible