도시 브레인

팡 교수는 Capital Grancel의 도시 브레인 프로그램에서 일한다. Grancel의 도로망은 무방향 그래프로 나타낼 수 있다. 처음에는 모든 도로의 제한 속도가 $1$ m/s이다. 팡 교수는 $1$달러를 써서 도로 하나의 제한 속도를 $1$ m/s 올릴 수 있다. 팡 교수에게는 $k$달러가 있으며, 각 도로에 0 이상의 정수 금액을 자유롭게 쓸 수 있다.

도로의 제한 속도가 $a$ m/s이면, 누구든 그 도로를 어느 방향으로 지나든 $1/a$초가 걸린다. 팡 교수가 돈을 다 쓴 뒤, Du 교수는 $s_1$에서 $t_1$으로, Wo 교수는 $s_2$에서 $t_2$로 이동한다. 팡 교수는 두 교수의 최소 이동 시간의 합이 가장 작아지도록 돈을 써야 한다.

$s_1$과 $t_1$은 최소 한 경로로 연결되어 있고, $s_2$와 $t_2$도 최소 한 경로로 연결되어 있다고 보장된다.

첫째 줄에 세 정수 $n$, $m$, $k$($1 \le n \le 5000$, $0 \le m \le 5000$, $0 \le k \le 10^9$)가 공백으로 구분되어 주어진다. $n$은 정점의 수, $m은 도로의 수,$k$는 가진 돈이다.

이어지는 $m$개의 줄에는 도로의 양 끝점 $a$와 $b$($1 \le a, b \le n$, $a \ne b$)가 주어진다. 같은 두 도시 사이에 도로가 여러 개 있을 수 있다.

마지막 줄에는 네 정수 $s_1$, $t_1$, $s_2$, $t_2$($1 \le s_1, t_1, s_2, t_2 \le n$)가 주어진다. 이는 Du 교수와 Wo 교수의 출발 도시와 도착 도시이다.

두 교수의 최소 이동 시간 합을 한 줄에 실수 하나로 출력한다. 절대 오차 또는 상대 오차가 $10^{-9}$ 이하이면 정답으로 인정한다.