페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8238
스페셜 저지

속도 제한 8s 128MB

문제

대한민국은 N개의 도시와 M개의 양방향 도로로 나타낼 수 있고, 각 도로에는 길이와 제한 속도가 정해져 있다.

장태환은 대통령 선거에서 서울 (1번 도시)에서 부산(N번 도시)까지 T시간 안에 이동이 가능하도록 하겠다는 공약을 걸고 당선되었다. 이제 공약을 실행할 차례이다.

그러나, 예산을 아껴야 하는 장태환은 새로운 도로를 건설할 수 없고, 모든 도로들의 속도 제한을 각각 xkm/h씩 올릴 수만 있다. (x는 0 이상의 실수)

x를 너무 크게 잡으면 교통사고가 늘어나 지지율이 떨어지기 때문에, 공약을 실행할 수 있는 최소 x를 구해야 한다.


입력

첫째 줄에 N,M,T가 주어진다(2\le N\le 10,000, 1\le M\le 100,000, 1 \le T\le 100,000)

둘째 줄부터 a,b(도로가 잇는 도시), l(도로의 길이), v(도로의 원래 제한 속도)가 주어진다.(1 \le a, b \le N, a \ne b, 1 \le l,v \le 100,000)

서울에서 부산까지 갈 수 있는 방법이 있다는 것이 보장된다.

입력으로 주어지는 모든 수는 자연수이다.


출력

첫째 줄에 최소 x를 출력하라. 절대/상대 오차는 10^{-6}까지 허용한다.


예제 

4 4 18
1 2 800 40
1 3 400 40
4 2 500 50
4 3 300 20
10


출처

BAPC 2023 Preliminaries
로그인해야 코드를 작성할 수 있어요.