세계의 빅맥

베시(Bessie)는 소 대학(cowllege)에서 가장 좋아하는 과목인 거시경제학을 공부하고 있다. 졸업 과제로 그녀는 전 세계 국가 간 환율에 대한 연구를 발표하려고 한다.

발표를 더 생동감 있게 만들기 위해, 베시는 세계 여러 나라의 빅맥 상대 가격을 보여주고 싶어 한다. 어떤 시작 국가에서의 빅맥 가격과, 한 나라의 통화를 다른 나라의 통화로 환전하는 환율 목록이 주어졌을 때, 목표 국가에서 얻을 수 있는 가장 낮은 빅맥 가격을 구하는 상황을 생각해 보자. 예를 들어:

• 미국에서 빅맥은 60 USD의 가치가 있다.
• USD에서 CAD로의 환율은 1 USD당 0.2 CAD이다.
• USD에서 GBP로의 환율은 1 USD당 5.00 GBP이다.
• GBP에서 CAD로의 환율은 1 GBP당 0.5 CAD이다.
• CAD에서 USD로의 환율은 1 CAD당 5.00 USD이다.

베시는 여러 번의 환전을 거쳐 도달할 수 있는, 캐나다에서의 가장 낮은 빅맥 가격을 알고 싶다. 경로는 두 가지가 있다:

• USD에서 CAD로 바로 환전: 60.00 USD × 0.2 CAD/USD = 12.00 CAD.
• USD에서 GBP를 거쳐 CAD로 환전: 60.00 USD × 5.00 GBP/USD × 0.5 CAD/GBP = 150.00 CAD.

베시는 150.00 CAD 대신 12.00 CAD를 내는 첫 번째 경로를 택할 것이다.

베시에게는 $1$부터 $N$까지 번호가 붙은 $N$개의 국가($1 \le N \le 2000$)와, 각각 국가 $i$에서 국가 $j$로 향하는 환율 $e_{ij}$($0.1 < e_{ij} \le 10$)의 목록 $M$개($1 \le M \le 25000$)가 주어진다($1 \le i \le N$; $1 \le j \le N$). 국가 $i$에서 국가 $j$로 환전하면 현재 가치에 $e_{ij}$가 곱해진다.

시작 국가 $A$($1 \le A \le N$)에서의 빅맥 가치 $V$($1 \le V \le 10^{12}$, 정수가 아닐 수도 있음)가 주어질 때, 여러 번의 환전을 거친 뒤 국가 $B$($1 \le B \le N$; $B \ne A$)에서 얻을 수 있는 가장 낮은 빅맥 가치를 구하라. 최솟값이 존재하지 않으면(가치를 얼마든지 작게 만들 수 있으면) 0을 출력한다.

정답이 0이 아니라면 1 이상 $10^{15}$ 이하임이 보장된다. 또한 어떤 나라의 통화에서든 다른 어떤 나라의 통화로도 도달할 수 있음이 보장된다.

• 첫째 줄: 공백으로 구분된 다섯 개의 수 $N$, $M$, $V$, $A$, $B$.
• 둘째 줄부터 $M+1$번째 줄까지: 하나의 환율을 나타내는, 공백으로 구분된 세 개의 수 $i$, $j$, $e_{ij}$.

• 국가 $B$에서 얻을 수 있는 가장 낮은 빅맥 가치를 소수점 아래 둘째 자리까지 반올림하여(0.5는 올림, round half up) 출력한다. 최솟값이 존재하지 않으면 0 하나만 출력한다.