시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 6 6 85.714%

문제

맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 최소값이다.

A에서 B로 가는 중복 비율은 A에서 B로 가는 모든 길을 동시에 이용했을 때 1시간 동안 B에 도착할 수 있는 차의 최대 개수와 길 1개를 이용했을 때 도착할 수 있는 최대 개수의 비율이다.

최소 중복 비율은 길 1개를 이용했을 때 도착할 수 있는 최대 개수가 가장 큰 값이 된다.

맨체스터의 도로 정보와 A, B가 주어졌을 때, 최소 중복 비율을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.

첫째 줄에 정수 4개가 주어진다. 차례대로 N, E, A, B이다. N(2 <= N <= 1,000)은 그래프의 정점의 개수, E(E>=1)는 간선의 개수이다. A(0<=A<N)와 B(0<=B<N, A!=B)는 문제 설명에 나와있는 A와 B이다.

그 다음 E개 줄은 각 간선에 대한 정보이다. 이 정보는 U V W로 구성되어 있는데, U와 V는 그래프의 정점이고, W는 U에서 V로 향하는 도로의 1시간에 지나갈 수 있는 차의 개수 제한이다.

출력

각 테스트 케이스에 대해 최소 중복 비율을 소수점 셋째자리까지 출력한다. 

예제 입력

1
7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9

예제 출력

1.667

힌트