Problem F
Negative Graph

It’s exam week. Once again, Victor spent so much time studying for exams he fell asleep without setting an alarm. As he hurriedly brushed his teeth and threw things into his bag, he checked when the next bus leaves. To his surprise, the app showed some trips where some legs of the journey took a negative amount of time. With the power of time travel he might make it in time! This must be the first time Västtrafik has actually been helpful, he thought. Can you help Victor find the shortest amount of time it takes to go to school?

Input

The input begins with one line containing the number of stations $N$, the number of routes $M$, the number of negative-time routes $K$, Victor’s home station $A$ and Chalmers’ station $B$ ($2\le N,M\le 10^5$, $0\le K\le 50$, $0\le A,B< N$) separated by spaces. Then there follows $M$ lines containing $a_ i$, $b_ i$, $c_ i$ ($0\le a_ i,b_ i<N$, $-10^9\le c_ i\le 10^9$) separated by spaces, denoting a bus route from station $a_ i$ to station $b_ i$ that takes $c_ i$ minutes. There are exactly $K$ negative $c_ i$. Self-loops and multiple edges are possible. It’s also possible that $A=B$.

Output

Output a single integer $C$, the shortest possible time (in minutes) it takes to go from station $A$ to $B$. Ignore time spent waiting for connections at stations. If the trip can be made arbitrarily short, output NEGATIVE INFINITY. If he can’t get to school at all, output POSITIVE INFINITY.

3 3 1 0 1
0 1 2
2 1 -2
0 2 3

1