A New Beginning

An extreme solar eruption has heated the Earth, causing a monstrous cataclysm. Tectonic plates are floating freely along the Earth's mantle; earthquakes with unseen magnitudes are causing metropolises to collapse to the ground; mountains are inundated by gigantic tsunamis; countries are turning to oceans of lava and volcanic dust.

It is 21 December 2012 and your only chance to save yourself and your family from the apocalypse is to reach the government ships in the Himalayas -- the modern arks that will save mankind. You have an airplane that flies with constant speed and a map with all standing airports. Unfortunately, not all pairs of airports are connected: enormous clouds of volcanic dust block some routes, while other airports are too far away from each other. Furthermore, not all airports have fuel available; some of them have nothing left but bare runways, and there you cannot refuel the aircraft. Since all means of navigation are destroyed, the only possible path between two airports is the shortest one (the great-circle arc on the sphere). On top of that, due to atmospheric instability and dramatic changes of air density, the fuel efficiency of the engines varies between flights, so the fuel consumption differs as well.

The good news is that you know between which airports it is possible to fly and how much fuel each flight costs, and also where you can refuel. All you have to do is find a way to get from your airport to the airport in the Himalayas as fast as possible. Write a program that computes the minimum amount of time required, given the coordinates of each airport and whether it has fuel, the fuel tank capacity of the airplane, the speed of the airplane, which pairs of airports are connected by a potential flight, and how much fuel each flight requires.

The first line contains four integers $N$, $M$, $V$, and $C$: the number of airports, the number of pairs of connected airports, the constant speed of the aircraft, and the fuel tank capacity, respectively.

The next $N$ lines describe the airports. Airports are points in 3-dimensional space, all lying on the surface of the Earth whose center is at the origin $(0, 0, 0)$. The $i$-th of these lines contains three real numbers and a Boolean $X_i$, $Y_i$, $Z_i$, and $R_i$: the coordinates of the $i$-th airport and whether you can refuel there ($R_i = 1$ means you can, $R_i = 0$ means you cannot).

The next $M$ lines describe the potential flights. Each pair of connected airports is unordered, i.e. a flight from $A$ to $B$ has the same properties as a flight from $B$ to $A$. The $k$-th of these lines contains three integers $A_k$, $B_k$, and $F_k$, denoting a potential flight between airport $A_k$ and airport $B_k$ that requires $F_k$ units of fuel (in either direction).

The last line contains two integers $S$ and $T$: the first and the last airport in your route.

Print the minimum time required to get from airport $S$ to airport $T$, rounded to exactly $10$ digits after the decimal point, on a single line.

If no route can be found, print the integer 0 on a single line instead.

• $2 \le N \le 1000$ — number of airports. Integer.
• $1 \le M \le 10000$ — number of possible flights. Integer.
• $1 \le V \le 1000$ — airplane's constant speed. Real number with up to $3$ digits after the decimal point.
• $1 \le C \le 1000$ — fuel tank capacity of the airplane. Integer.
• $-100 \le X_i, Y_i, Z_i \le 100$ — coordinates of the $i$-th airport. Real numbers with up to $18$ digits after the decimal point. Moreover, $X_i^2 + Y_i^2 + Z_i^2$ is constant for all $i$, i.e. all airports lie at the same distance from the Earth's center within a given test case.
• The number of airports where you can refuel is between $1$ and $20$, inclusive.
• The Earth's radius is an integer $\ge 1$.
• $1 \le A_k, B_k \le N$ — airports in the $k$-th potential flight. Different integers. Each unordered pair appears at most once in the input.
• $1 \le F_k \le C$ — amount of fuel used by the airplane on the $k$-th flight. Integer.

Notes:

• A direct flight between two airports follows the shortest arc on the sphere (the great-circle arc) connecting them. Even if more than one such arc exists, only the distance matters.
• No potential flight is shorter than $10^{-6}$.
• Due to precision errors, the distance from the Earth's center may differ slightly between airports, but the absolute difference between that distance and the Earth's radius is at most $10^{-10}$; thus the correctness of an algorithm is unaffected if all airports are considered to lie exactly on the Earth's surface.
• $R_S = 1$, i.e. the fuel tank is always full at the beginning. Also, each time you visit an airport with fuel, the tank is filled up again.
• The time required for landing, refueling, taking off, and accelerating is negligibly small and considered to be $0$.
• Potential flights are completely independent. If the arc of a flight from $A$ to $B$ happens to pass through some airport $C$, this does not imply a flight between $A$ and $C$, nor between $B$ and $C$.

Consider the following situation. The Earth's radius is $5$, the airplane's speed is $2.5$, and the fuel tank capacity is $9$; you must get from airport $1$ to airport $3$. You can refuel at airports $1$ and $6$.

The direct routes $1 \to 2 \to 3$ and $1 \to 4 \to 3$ consume $13$ and $10$ units of fuel respectively, both exceeding the tank capacity of $9$. In fact, every route from $1$ to $3$ without refueling needs more than $9$ units, so your only option is to refuel at airport $6$.

There are three routes to airport $6$: $1 \to 2 \to 6$, $1 \to 4 \to 6$, and $1 \to 5 \to 2 \to 6$; the first two are the shortest. After filling the tank at $6$, going straight through $2$ toward $3$ leaves you exactly $1$ unit short of fuel. The only way is through $4$: you reach $3$ with the tank empty, but you are saved.

The optimal routes are therefore $1 \to 2 \to 6 \to 4 \to 3$ and $1 \to 4 \to 6 \to 4 \to 3$. Both consist of four $90^\circ$ arcs, so their total length equals the Earth's equator, $2\pi R$. Consequently, the required time is $2\pi R / V \approx 12.5663706144$.