베시는 그녀가 가장 좋아하는 과목인 거시경제학을 공부하고 있다. 소들의 대학에서 그녀는 기말 과제를 하고 있었다. 그녀는 전세계 국가들 사이의 환율에 대해 발표할 예정이다. 그녀의 발표를 더 생생하게 하기 위해 그녀는 전세계의 빅맥에 대한 상대적인 가격을 보여주고 싶어한다. (비록 빅맥이 좋은 것은 아닐지라도 말이다.) 이것을 발표하기 위해 그녀는 한 국가에서 빅맥의 최소가격을 찾고싶어한다. 각각의 국가들 사이의 환율을 통해 빅맥의 최소가격이 얼마인지 계산할 수 있다. 다음의 예시를 보자.

• 미국에서 빅맥이 60달러이다.
• 미국의 1달러는 캐나다의 0.2 캐나다달러와 같다.
• 미국의 1달러는 영국의 5파운드와 같다.
• 영국의 1파운드는 캐나다의 0.5 캐나다달러와 같다.
• 캐나다의 1캐나다달러는 미국의 5달러와 같다.

• 미국돈을 캐나다돈으로 바로 환전하면 60*0.2=12 캐나다달러이다.
• 미국돈을 영국돈을 거쳐 캐나다돈으로 환전하면 60*5*0.5=150 캐나다달러이다.

A (1 <= A <= N) 국가의 빅맥의 가격 V (1 <= V <= 1,000,000,000,000) 이 주어질 때, 그녀를 도와 B (1<=B<=N, B!=A) 국가의 빅맥 가격의 최소를 구하자. (반드시 정수일 필요는 없다.) 만약 최소가 존재하지 않으면 0 을 출력한다.

답이 0 이 아닐 경우에 1 에서 10^15 사이인 것은 보장된다. 또한 서로 다른 국가 사이에 환전이 가능한 것도 보장된다.

입력

• 첫 줄에 다섯 개의 숫자가 주어진다. (N, M, V, A, B)
• 두번째 줄부터 M 줄 동안 3개의 수로 환율 정보가 주어진다. (i, j, e_ij)

출력

입출력 예

입력

3 4 60 1 2
1 2 0.2
1 3 5
3 2 0.5
2 1 5

출력

12.000000

출처: USACO 2010 DEC gold
번역: KangJ