题目描述

一场极端太阳风暴引发了全球性灾难。你唯一的生机，是驾驶飞机前往喜马拉雅山中的政府方舟机场。

你掌握的信息如下：

• 飞机以恒定速度飞行；
• 世界上仍有 N 个机场；
• 某些机场之间存在“可飞行航线”，但并不是任意两机场之间都可以直接飞行；
• 有些机场可以加油，有些不行；
• 每条可飞行航线都会消耗一定量燃料；
• 由于导航系统全部失效，从一个机场到另一个机场的飞行路径只能取它们在地球表面之间的最短球面弧；
• 每次到达有油机场时，油箱会被重新加满；初始机场也保证能加满油。

请你计算：从起点机场 S 到终点机场 T 的最短时间是多少。

输入格式

第一行包含四个数：N M V C，分别表示：

• N：机场数量；
• M：可飞行机场对数量；
• V：飞机恒定速度；
• C：油箱容量。

接下来 N 行，每行给出一个机场的信息：Xi Yi Zi Ri：

• (Xi, Yi, Zi) 是该机场在三维空间中的坐标；
• Ri 为布尔值，Ri = 1 表示该机场可加油，Ri = 0 表示不可加油。

所有机场都位于以原点为球心的同一球面上（即地球表面）。

接下来 M 行，每行给出一个潜在航线：Ak Bk Fk，表示：

• 机场 Ak 与 Bk 之间可双向飞行；
• 无论方向如何，飞这一段都会消耗 Fk 单位燃料。

最后一行给出 S T，表示起点和终点机场编号。

输出格式

输出一个实数，表示从 S 到 T 所需的最短时间。

如果无路可达，输出 0。

当你的答案与标准答案绝对误差不超过 1e-4 时，视为正确。

数据范围

• 2 <= N <= 1000
• 1 <= M <= 10000
• 1 <= V <= 1000，实数，小数点后最多 3 位
• 1 <= C <= 1000
• -100 <= Xi,Yi,Zi <= 100，实数，小数点后最多 18 位
• 可加油机场数量满足 1 <= count <= 20
• 地球半径至少为 1
• 1 <= Ak,Bk <= N，且 Ak != Bk
• 每对无序机场在输入中至多出现一次
• 1 <= Fk <= C

说明

• 一条直飞航线的长度定义为两机场之间在球面上的较短大圆弧长；
• 不会有长度小于 1e-6 的航线；
• 由于精度误差，不同机场到球心的距离可能有极微小差异，但可以视为都在同一球面上；
• R_S = 1，即起点机场一定可以加油，出发时油箱是满的；
• 降落、加油、起飞、加速耗时均忽略不计；
• 即使某条从 A 到 B 的球面弧经过某机场 C，也不代表 A 与 C 或 B 与 C 之间存在潜在航线。

部分分

在 40% 的测试中，N <= 8。

样例

输入

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

样例解释

地球半径为 5，飞机速度为 2.5，油箱容量为 9。目标是从 1 号机场到 3 号机场。

显然不能直接走 1-2-3 或 1-4-3，因为对应耗油分别为 13 和 10，都超过油箱容量。事实上，所有完整路线的总耗油都超过 9，因此唯一希望是中途在 6 号机场加油。

到达 6 的较短可行路线有两条：1-2-6 和 1-4-6（1-5-2-6 更长）。加油后若去 2，仍无法继续到 3；唯一可行方式是经 4 到 3。

因此最优路线为：

• 1-2-6-4-3
• 1-4-6-4-3

它们都由 4 段 90° 的球面弧组成，总长度等于地球赤道周长 2πR，因此总时间为：