Rakunarok

현실 세계에 깊이 실망한 당신은 남은 인생을 MMORPG(Massively Multi-Player Online Role Playing Game) 세계에서 살기로 결심했다. 게임에 쏟는 시간은 이제 문제가 아니다. 당신에게 필요한 것은 오직 효율이다.

어느 날 한 마을에서 다른 마을로 이동해야 한다. 이 게임에서는 일부 마을 쌍이 도로로 연결되어 있고, 플레이어는 그 도로를 따라 이동할 수 있다. 도로에서는 각종 몬스터가 플레이어를 습격한다. 하지만 당신은 고레벨 플레이어이므로 몬스터는 경험치 공급원일 뿐이다. 모든 도로는 양방향이다. 경로는 마을의 나열로 표현되며, 연속한 두 마을은 도로로 연결되어 있다.

당신은 목적지 마을까지 가장 효율적인 경로로 이동하려 한다. 여기서 경로의 효율은 경로에서 얻는 총 경험치를 경로를 이동하는 데 필요한 시간으로 나눈 값이다.

당신의 목적은 이동이지 훈련이 아니므로, 순조로운 경로만 선택한다. 경로가 순조롭다는 것은 경로에서 연속한 두 마을에 대해 뒤쪽 마을이 앞쪽 마을보다 목적지에 더 가깝다는 뜻이다. 두 마을의 거리는 한 마을에서 다른 마을로 이동하는 데 필요한 최단 시간으로 측정한다.

효율이 가장 높은 경로를 찾는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 수 c가 주어진다.

각 테스트 케이스의 첫째 줄에는 마을과 도로의 수를 나타내는 두 정수 n과 m이 주어진다. 다음 줄에는 시작 마을과 목적지 마을을 나타내는 두 정수 s와 t가 주어진다. 그다음 m개의 줄이 주어진다. i번째 줄에는 네 정수 ui, vi, ei, ti가 주어지는데, ui와 vi는 i번째 도로로 연결된 두 마을이고, ei는 얻을 수 있는 경험치, ti는 그 도로를 통과하는 데 필요한 시간이다.

각 마을은 0부터 (n - 1)까지의 마을 번호로 나타낸다. 시작 마을과 목적지 마을은 절대 일치하지 않는다. n, m, ei, ti는 양수이고 1000 이하이다.

각 테스트 케이스마다 가능한 가장 높은 효율을 한 줄에 출력한다. 답은 소수점 이하 네 자리까지 출력한다. 답의 오차는 10-4보다 클 수 없다.