JUNGOL

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

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

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

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

Entrada

첫째 줄에 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)

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

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

Salida

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

Ejemplo

Etiqueta

Fuente

BAPC 2023 Preliminaries

속도 제한 8s 128MB