새로운 시작

극심한 태양 폭발로 지구가 뜨겁게 달아올라 거대한 재난이 일어났습니다. 지각판이 맨틀 위를 자유롭게 떠다니고, 유례없는 규모의 지진이 대도시를 무너뜨리며, 거대한 쓰나미가 산을 삼키고, 여러 나라가 용암과 화산재의 바다로 변해 갑니다.

2012년 12월 21일, 당신과 가족이 종말에서 살아남을 유일한 기회는 히말라야에 있는 정부의 방주, 즉 인류를 구할 현대판 방주에 도달하는 것입니다. 당신에게는 일정한 속도로 나는 비행기 한 대와, 아직 남아 있는 모든 공항이 표시된 지도가 있습니다. 하지만 모든 공항 쌍이 연결되어 있는 것은 아닙니다. 어떤 항로는 거대한 화산재 구름에 막혀 있고, 어떤 공항들은 서로 너무 멀리 떨어져 있습니다. 게다가 모든 공항에서 급유할 수 있는 것도 아닙니다. 어떤 공항에는 텅 빈 활주로만 남아 있어 연료를 채울 수 없습니다. 모든 항법 장비가 파괴되었으므로, 두 공항을 잇는 유일한 비행 경로는 최단 경로(구면 위의 대원 호)뿐입니다. 여기에 더해 대기 불안정과 급격한 공기 밀도 변화 때문에 비행마다 엔진의 연료 효율이 달라져 연료 소모량도 제각각입니다.

다행히도 당신은 어떤 공항 사이를 비행할 수 있는지, 그 비행에 드는 연료량은 얼마인지, 그리고 어디에서 급유할 수 있는지를 알고 있습니다. 이제 출발 공항에서 히말라야 공항까지 최대한 빨리 가는 방법만 찾으면 됩니다. 각 공항의 좌표와 급유 가능 여부, 연료 탱크 용량, 비행기의 속도, 어떤 공항 쌍이 비행으로 연결되는지, 각 비행에 필요한 연료량이 주어질 때, 출발 공항에서 목적지 공항까지 가는 데 필요한 최소 시간을 구하는 프로그램을 작성하세요.

첫째 줄에 네 정수 $N$, $M$, $V$, $C$가 주어집니다. 각각 공항의 수, 비행으로 연결된 공항 쌍의 수, 비행기의 일정한 속도, 연료 탱크 용량을 뜻합니다.

이어지는 $N$개의 줄에는 공항 정보가 주어집니다. 모든 공항은 중심이 원점 $(0, 0, 0)$인 지구의 표면 위 한 점으로 표현됩니다. 이 중 $i$번째 줄에는 세 실수와 한 정수 $X_i$, $Y_i$, $Z_i$, $R_i$가 주어집니다. 앞의 세 값은 $i$번 공항의 좌표이고, $R_i$는 급유 가능 여부입니다($R_i = 1$이면 급유 가능, $R_i = 0$이면 불가능).

그다음 $M$개의 줄에는 가능한 비행 정보가 주어집니다. 연결된 공항 쌍에는 순서가 없습니다. 즉, $A$에서 $B$로 가는 비행과 $B$에서 $A$로 가는 비행은 성질이 같습니다. 이 중 $k$번째 줄에는 세 정수 $A_k$, $B_k$, $F_k$가 주어지며, $A_k$번 공항과 $B_k$번 공항 사이를 오가는 비행에 $F_k$만큼의 연료가 필요함을 뜻합니다(양방향 모두 동일).

마지막 줄에는 두 정수 $S$와 $T$가 주어집니다. 각각 경로의 출발 공항과 도착 공항입니다.

출발 공항 $S$에서 도착 공항 $T$까지 가는 데 필요한 최소 시간을, 소수점 아래 정확히 $10$자리까지 반올림하여 한 줄에 출력하세요.

도달할 수 있는 경로가 전혀 없다면 한 줄에 정수 0을 출력하세요.

• $2 \le N \le 1000$ — 공항의 수. 정수.
• $1 \le M \le 10000$ — 가능한 비행의 수. 정수.
• $1 \le V \le 1000$ — 비행기의 일정한 속도. 소수점 아래 최대 $3$자리까지의 실수.
• $1 \le C \le 1000$ — 연료 탱크 용량. 정수.
• $-100 \le X_i, Y_i, Z_i \le 100$ — $i$번 공항의 좌표. 소수점 아래 최대 $18$자리까지의 실수. 또한 모든 $i$에 대해 $X_i^2 + Y_i^2 + Z_i^2$의 값은 일정합니다. 즉, 한 입력 안에서 모든 공항은 지구 중심으로부터 같은 거리에 있습니다.
• 급유가 가능한 공항의 수는 $1$개 이상 $20$개 이하입니다.
• 지구의 반지름은 $1$ 이상의 정수입니다.
• $1 \le A_k, B_k \le N$ — $k$번 비행에 등장하는 두 공항. 서로 다른 정수. 각 (순서 없는) 공항 쌍은 입력에 최대 한 번만 나타납니다.
• $1 \le F_k \le C$ — $k$번 비행에서 소모되는 연료량. 정수.

추가 사항:

• 두 공항 사이의 직항 비행 경로는 지구 표면(구면) 위에서 두 점을 잇는 가장 짧은 호, 즉 대원 호입니다. 그런 호가 둘 이상 있더라도 중요한 것은 거리뿐입니다.
• 어떤 비행도 그 호의 길이가 $10^{-6}$보다 짧지 않습니다.
• 정밀도 오차로 인해 공항마다 지구 중심까지의 거리가 미세하게 다를 수 있지만, 그 거리와 지구 반지름의 절대 차이는 $10^{-10}$ 이하입니다. 따라서 모든 공항이 정확히 지구 표면 위에 있다고 간주해도 알고리즘의 정확성에는 아무런 영향이 없습니다.
• $R_S = 1$입니다. 즉, 처음에 연료 탱크는 항상 가득 차 있습니다. 또한 급유가 가능한 공항을 방문할 때마다 탱크가 다시 가득 찹니다.
• 착륙, 급유, 이륙, 가속에 드는 시간은 무시할 만큼 작아 $0$으로 간주합니다.
• 각 비행은 서로 완전히 독립적입니다. $A$에서 $B$로 가는 비행의 호가 우연히 어떤 공항 $C$를 지나더라도, 그것이 $A$와 $C$ 사이 또는 $B$와 $C$ 사이에 비행이 존재함을 뜻하지는 않습니다.

다음과 같은 상황을 생각해 봅시다. 지구의 반지름은 $5$, 비행기의 속도는 $2.5$, 연료 탱크 용량은 $9$이며, 공항 $1$에서 공항 $3$으로 가야 합니다. 급유가 가능한 공항은 $1$번과 $6$번입니다.

직항으로 이어지는 경로 $1 \to 2 \to 3$과 $1 \to 4 \to 3$의 연료 소모량은 각각 $13$과 $10$으로, 둘 다 탱크 용량 $9$를 넘습니다. 사실 급유 없이 $1$에서 $3$까지 가는 모든 경로는 $9$보다 많은 연료를 필요로 하므로, 유일한 방법은 $6$번 공항에서 급유하는 것입니다.

$6$번 공항에 도달하는 경로는 $1 \to 2 \to 6$, $1 \to 4 \to 6$, $1 \to 5 \to 2 \to 6$의 세 가지이며, 이 중 앞의 두 경로가 더 짧습니다. $6$번에서 탱크를 가득 채운 뒤 곧바로 $2$번을 거쳐 $3$번으로 가려 하면 연료가 $1$만큼 모자랍니다. 따라서 $4$번을 거쳐야 하며, $3$번에 도착할 때 연료는 정확히 바닥나지만 무사히 도착할 수 있습니다.

결국 최적 경로는 $1 \to 2 \to 6 \to 4 \to 3$ 또는 $1 \to 4 \to 6 \to 4 \to 3$이며, 두 경로 모두 네 개의 $90^\circ$ 호로 이루어져 총 길이가 지구 적도 둘레인 $2\pi R$과 같습니다. 따라서 걸리는 시간은 $2\pi R / V \approx 12.5663706144$입니다.