题目描述

传说 2012-12-21 是世界末日啊！（虽然今天已经是 2012-12-26了……）人们都要逃亡了。到处都是自然灾害，导致地球上只有 $n$ 个地方可以存活了。其中，我们在 $s$ 号点，喜马拉雅山在 $t$ 号点。对于这 $n$ 个点，我们会用 $(X_{i},Y_{i},Z_{i})$ 来描述这些点，而坐标原点则是地球中心。显然，这 $n$ 个地点是不会靠在一起的，那么我们必须要用飞机来飞行。已知我们所坐的飞机会保持一个恒定的速度 $v$，并有一个容量为 $c$ 的油箱。刚出发时，油箱是满的。而这 $n$ 个点之中，不是能够两两之间互相飞行的。可以飞的航线只有 $m$ 条，而每一条所需的油量都不一样（双向航线）。更糟糕的是，不是所有的点都能加油，那么就意味着飞行员每到一个地点，就不得不把油加满！已知两点之间的距离为坐标之间的球面距离（因为是在地球上嘛），而飞行总时间为(总距离 $/v$)，那么我们要从 $s$ 号点飞到 $t$ 号点至少需要多少时间呢？答案保留 $10$ 位小数。

【注意事项】 1.     两点之间的距离为最短球面距离，可能有不止一条，但是只有一条有用。 2.     a, b之间的航线可能中途经过c点，但这不代表a和c之间或b和c之间有航线。 3.     起飞，降落，加油等时间都可无视。 4.     若无解，则输出0. 5.     若|你输出的答案-标准答案|<=1e-4，则算正确。

输入格式

第1行四个正数 $n, m, v, c$。   接下来 $n$ 行，每行四个数，X_{i}, Y_{i}, Z_{i}, R_{i}，其中 $R_{i}=1$ 表示该点可加油，$R_{i}=0$ 表示该点不可加油。

接下来 $m$ 行，每行 $3$ 个正整数，$A_{k}, B_{k}, C_{k}$，其中 $A_{k}, B_{k}$ 表示第 $k$ 条航线所连接的两个站点。$C_{k}$ 表示该航线所需油量。    最后1行，两个正整数，$s$ 和 $t$。

输出格式

仅一行，为所需最短时间。若无法到达 $t$ 号点，则输出 0.

6 9 2.5 9
0.0 5.0 0.0 1
0.0 0.0 -5.0 0
0.0 -5.0 0.0 0
0.0 0.0 5.0 0
3.0 4.0 0.0 0
4.0 3.0 0.0 1
1 2 5
2 3 8
1 4 5
4 3 5
1 5 1
5 6 9
5 2 1
2 6 2
6 4 4
1 3

12.5663706144

数据规模与约定

对于 $100 \%$ 的数据，$2\ leq n\leq 1\times 10^3$，$1 \leq m \leq 1\times 10^4$， $1 \leq v \leq 1 \times 10^3$，为实数，精度最高为 $1\times 10^{-3}$。 $1 \leq c \leq 1\times 10^3$。$-100 \leq X_{i},Y_{i},Z_{i} \leq 100$，实数，精度最高为 $1\times 10^{-18}$，表示第 $i$ 个点的坐标，其中数据保证 $X_{i}^{2}+Y_{i}^{2}+Z_{i}^{2}$（即地球半径）为一个恒定的正整数（尽管存在精度差，但是|精度差|$\leq 1^{-10}$，因此可认为每个点都严格在地球表面）。并保证，任意航线的长度 $\geq 1\times 10^{-6}$。 $1\leq {\text 可加油的站点数量}\leq 20$，$1\leq {\text 地点的编号} \leq n$，$1\leq {\text 航线所需油量}\leq c$。