该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在经典电影《异次元杀阵》中，玩家们会被关进一个 $3D$ 魔方形状的迷宫房间，每个房间中存在一些机关，玩家们需要找到一条安全的通道离开这个迷宫。

徐老师受到这个电影的启发，决定制作一款名为《异次元杀阵·plus》的逃生游戏！

这个游戏设置在一个三维空间中，其中某些坐标点会存在有房间，并且房间之间存在一些本身已经存在的双向原有通道（即两个房间可以互相到达），而玩家的目的则是从起点 $1$ 号房间逃到出口 $n$ 号房间。

而这个游戏有两大难点："门" 和 "清毒器"

一、 关于 "门"

在每个房间生成时，会同时生成随机数量的 "门"，如果两个房间 $A,B$ 都存在 "门"，则玩家可以新建一条通道使得这两个房间中的一扇门相连，但是一扇门只能使用一次，也就是一扇门连接通道后，就不能再和其他房间的其他门连接通道了，并且这次新建通道需要花费的资源等于 $A,B$ 在三维空间中直线距离（原有通道不占用 "门"）。

形式化的说，如果有三个房间 $A,B,C$，坐标分别为$A(x_A,y_A,z_A),B(x_B,y_B,z_B),C(x_C,y_C,z_C)$，并且分别有 $2,1,2$ 个门

那么玩家可以新建通道连接房间 $A,B$，花费 $\sqrt{(x_A-x_b)^2+(y_A-y_B)^2+(z_A-z_B)^2}$ 单位的资源，此时三个房间剩余的门分别为 $1,0,2$

此时玩家可以选择新建通道连接房间 $A,C$，但是无法继续新建通道连接房间 $B,C$，因为房间 $B$ 已经没有空余的门了。

二、 关于 "清毒器"

徐老师为了加大游戏难度，他在所有房间中都注入了 "毒气"，而玩家无法在有 "毒气" 的房间。

玩家有一台 "清毒器"，可以向房间里注入"解毒气体"，我们认为只要这个房间注入了 "解毒气体"，那么这个房间就是安全的，玩家可以进入。

但是 "清毒器" 只能向 $1$ 号房间注入 "解毒气体"，其余房间需要靠空气压强通过原有通道和玩家新建的通道传递扩散过去，好在玩家可以提前将 "清毒器" 的气体压强设置为任意数值。

形式化的说，如果设置 "清毒器" 的压强为 $x$，那么 "解毒气体" 能够从 $1$ 号房间开始顺着所有通道扩散，但是最高只能扩散到高度为 $x$ 房间，例如下图。

如果给 "清毒器" 设置的压强为 $3$，最终房间 $1,2,3,4$ 会被注入 "解毒气体"

如果给 "清毒器" 设置的压强为 $4$，最终房间 $1,2,3,4,6,7$ 会被注入 "解毒气体"

同时徐老师还设置了一个小小的坑点：如果 "解毒气体" 传递到了某个房间，但是这个房间有空余的门，则会导致气体溢出，使得所有 "解毒气体" 无效！

所以玩家也可以选择花费 $0.3$ 单位的资源关闭指定房间的一扇门。

现在徐老师想知道，对于一场已经设计好的游戏场景，玩家最少需要花费多少资源，才能够保证 "解毒气体" 从 $1$ 号房间扩散到 $n$ 号房间。

输入格式

输入第一行包含两个整数 $n,m$ 表示有 $n$ 个房间，$m$ 个原有通道

接下来 $n$ 行，每行包含四个整数 $x_i,y_i,z_i,door_i$，分别表示第 $i$ 个房间的坐标（其中 $z_i$ 表示三维坐标中的高度，$door_i$表示这个房间 "门" 的数量）

接下来 m 行，每行两个整数 $u_i,v_i$ 表示一条原有通道，连接的是 $u_i,v_i$ 两个房间。

输出格式

输出一个实数（保留四位小数）表示玩家最少需要花费多少单位的资源才能使得 "解毒气体" 从 $1$ 号房间扩散到 $n$ 号房间

如果这局游戏是一个死局，即无法扩散到 $n$ 号房间，则输出 "impossible"（不包含引号）

数据范围

对于所有数据满足 $0 \leq m \leq 50000, -10000 \leq x_i,y_i,z_i \leq 10000, 0 \leq door_i \leq 400, 1 \leq u_i < v_i \leq n$。

保证任意两个房间之间最多只会存在一条原有通道，且不会有两个房间坐标相同。

样例输入1

7 7
0 0 0 1
0 2 2 1
0 4 3 1
0 2 3 1
0 1 5 1
0 0 3 1
0 2 4 1
1 2
1 3
1 4
3 4
4 7
6 7
5 7

样例输出1

1.8000

样例解释1

由于本身就已经有通道连接了，所以只需要将 "清毒器" 的压强设置为 $4$，即可使得 $1,2,3,4,6,7$ 被扩散到气体，但是需要封闭这 $6$ 个房间的所有门防止气体溢出，则需要花费 $6 * 0.3 = 1.8$ 单位的气体

样例输入2

4 1
2 0 0 0
3 0 1 0
4 1 0 1
5 1 1 1
1 2

样例输出2

impossible

样例解释2

由于房间 $1$ 只和房间 $2$ 连通，而 $1$ 和 $2$ 都没有 "门"，所以无法连接到房间 $4$。

样例输入3

7 6
2 0 1 5
3 0 0 5
1 1 4 5
3 0 4 5
5 2 1 5
3 3 2 5
5 1 3 5
1 2
1 3
3 4
4 7
5 7
6 7

样例输出3

9.9000