음수 그래프

시험 기간이다. Victor는 또다시 시험공부에 너무 많은 시간을 쓴 나머지 알람을 설정하지 않고 잠들어 버렸다. 서둘러 이를 닦고 가방에 물건을 챙겨 넣으면서, 그는 다음 버스가 언제 출발하는지 확인했다. 놀랍게도 앱에는 여정의 일부 구간에 음수의 시간이 걸리는 경로가 몇 개 표시되어 있었다. 시간 여행의 힘이 있다면 제시간에 도착할 수도 있다! Västtrafik이 실제로 도움이 된 것은 이번이 처음임이 틀림없다고 그는 생각했다. Victor가 학교에 가는 데 걸리는 가장 짧은 시간을 찾도록 도와줄 수 있는가?

입력은 역의 수 $N$, 노선의 수 $M$, 음수 시간 노선의 수 $K$, Victor의 집이 있는 역 $A$, Chalmers가 있는 역 $B$ ($2\le N,M\le 10^5$, $0\le K\le 50$, $0\le A,B< N$)가 공백으로 구분되어 있는 한 줄로 시작한다. 그다음에는 $a_i$, $b_i$, $c_i$ ($0\le a_i,b_i<N$, $-10^9\le c_i\le 10^9$)가 공백으로 구분되어 있는 $M$개의 줄이 주어지며, 이는 역 $a_i$에서 역 $b_i$까지 $c_i$분이 걸리는 버스 노선을 나타낸다. 음수인 $c_i$는 정확히 $K$개이다. 자기 루프와 다중 간선이 존재할 수 있다. 또한 $A=B$일 수도 있다.

역 $A$에서 $B$까지 가는 데 걸릴 수 있는 가장 짧은 시간(분)인 하나의 정수 $C$를 출력한다. 역에서 환승을 기다리는 데 걸리는 시간은 무시한다. 이동 시간을 임의로 짧게 만들 수 있다면 NEGATIVE INFINITY를 출력한다. 학교에 전혀 갈 수 없다면 POSITIVE INFINITY를 출력한다.