자전거 훈련 경로

다가오는 올림픽을 준비하기 위해, 당신은 국가 사이클 대표팀의 자전거 훈련 경로를 제안하는 일을 맡았습니다. 훈련 위원회는 전국 여러 장소에서 두 지점 사이를 이동하는 경로들을 찾고자 하며, 각 경로는 언덕의 경사에 따라 정해지는 원하는 난이도를 가져야 합니다.

고도 정보가 함께 표시된 도로 지도가 주어집니다. 두 개 이상의 도로가 만나는 각 교차점은 $x$, $y$, $z$ 좌표로 나타냅니다. 각 도로는 교차점에서 시작하여 교차점에서 끝나는 직선이며, 다른 도로 위를 지나는 다리나 아래를 지나는 터널을 포함하지 않습니다. 도로는 어느 방향으로든 주행할 수 있고, 그 난이도는 주행 방향에 따라 달라집니다.

도로를 주행하는 난이도 $d$는, 도로가 평지이거나 내리막 방향으로 주행하는 경우 $0$입니다. 평지가 아닌 도로를 오르막 방향으로 주행할 때의 난이도는 $\lfloor 100 \cdot \text{rise} / \text{run} \rfloor$이며, 여기서 rise는 고도 변화의 절댓값, run은 두 끝점을 고도 $0$ 평면에 수평 투영했을 때의 거리입니다. (내리막 도로를 주행하는 난이도는 항상 $0$입니다.)

도로의 길이는 두 끝점 사이의 직선(3차원 유클리드) 거리입니다. 경로는 각 도로가 이전 도로가 끝난 교차점에서 이어지는 도로들의 나열이며, 경로의 길이는 그 도로들의 길이의 합입니다. 경로에 속한 모든 도로의 난이도 중 최댓값이 $d$일 때 그 경로의 난이도는 $d$입니다. 선택한 두 지점에 대해, 위원회는 요구된 난이도를 가지면서 전체 길이가 가장 짧은 경로를 원합니다.

참고: 바닥 함수 $\lfloor X \rfloor$는 $X$를 정수로 내림한 값을 의미합니다.

아래 그림은 예제 입력에 해당하는, 세 개의 교차점을 가진 도로 지도를 보여 줍니다.

더 진하게 칠해진 면의 변 레이블은 오르막 난이도를 나타냅니다. 더 옅게 칠해진 면은 고도 $0$ 평면으로의 수평 투영입니다.

입력은 여러 개의 도로 지도로 이루어집니다. 각 지도는 공백으로 구분된 두 음이 아닌 정수 $N$과 $M$이 한 줄에 주어지는 것으로 시작하며, 각각 교차점의 수와 도로의 수를 의미합니다 ($0 < N, M \le 10000$). $N$과 $M$이 모두 $0$인 줄은 입력의 끝을 나타냅니다.

이어지는 $N$개의 줄에는 각각 공백으로 구분된 세 정수가 주어지며, 이는 한 교차점의 $x$, $y$, $z$ 좌표입니다. 각 좌표는 $0$ 이상 $10000$ 이하입니다. 교차점은 나타나는 순서대로 $1$번부터 번호가 매겨집니다. 이어지는 $M$개의 줄에는 각각 두 정수가 주어지며, 이는 한 도로의 두 끝 교차점입니다 (도로는 어느 방향으로든 주행할 수 있습니다).

마지막으로 세 정수 $s$, $t$, $d$가 한 줄에 주어지며, 훈련 경로의 출발 교차점 $s$, 도착 교차점 $t$, 요구 난이도 $d$를 의미합니다 ($0 \le d \le 10$). 유효한 훈련 경로는 난이도가 정확히 $d$인 도로를 하나 이상 포함해야 하고, 난이도가 $d$보다 큰 도로를 포함해서는 안 됩니다. 경로가 닫힌 순환이라면 $s$와 $t$는 같은 교차점입니다.

각 도로 지도에 대해 다음 중 하나를 한 줄에 출력합니다.

1. 유효한 훈련 경로의 가장 짧은 길이를 소수점 아래 정확히 세 자리로 반올림한 값 (항상 소수점 아래 세 자리를 모두 출력합니다), 또는
2. 실행 가능한 경로가 없으면 단어 None.

참고 — 양수 R.xxxy를 소수점 아래 세 자리로 반올림하는 방법:

• 넷째 소수 자리 y가 5보다 작으면 결과는 R.xxx입니다.
• 그렇지 않으면 결과는 R.xxx에 0.001을 더한 값입니다.

예를 들어 10.3463은 10.346으로, 10.3695는 10.370으로 출력됩니다.