맨체스터의 도로

맨체스터의 모든 도로는 방향이 있는 일방통행 도로이다. 각 도로에는 한 시간 동안 지나갈 수 있는 자동차 수의 제한이 있다. 한 경로의 용량은 그 경로에 포함된 도로들의 제한값 중 최솟값이다.

A에서 B로 가는 중복 비율은 두 값을 나눈 것이다. 분자는 A에서 B로 가는 여러 경로를 동시에 사용할 때 한 시간 동안 B에 도착시킬 수 있는 자동차 수의 최댓값이다. 분모는 경로 하나만 사용할 때 한 시간 동안 B에 도착시킬 수 있는 자동차 수의 최댓값이다.

중복 비율을 최소로 하려면, 경로 하나만 사용할 때의 값은 가능한 한 커야 한다. 즉, 모든 A에서 B로 가는 경로 중 용량이 가장 큰 경로를 분모로 사용한다.

도로 정보와 정점 A, B가 주어졌을 때 최소 중복 비율을 구하시오.

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 다음 형식이다.

첫 줄에는 정수 N, E, A, B가 이 순서대로 주어진다. N (2 ≤ N ≤ 1,000)은 그래프의 정점 수이고, E (E ≥ 1)는 간선 수이다. A (0 ≤ A < N)와 B (0 ≤ B < N, A ≠ B)는 출발 정점과 도착 정점이다.

이어지는 E개 줄에는 각 도로의 정보 U V W가 주어진다. U (0 ≤ U < N)와 V (0 ≤ V < N, V ≠ U)는 도로가 U에서 V로 향함을 뜻하고, W (1 ≤ W ≤ 1000)는 그 도로를 한 시간 동안 지나갈 수 있는 자동차 수의 제한이다.

각 테스트 케이스마다 최소 중복 비율을 한 줄에 출력한다. 값은 소수점 아래 셋째 자리까지 출력한다.