Problem H
Harry the Hamster

Image by Bill McChesney.

Harry the Hamster lives in a giant hamster cage. Inside the cage there is a set of $n$ plastic balls connected by unidirectional hamster tubes of varying lengths. Harry is currently in ball $s$ and his bed is in ball $t$.

Being a simple hamster, the hemispheres of Harry’s brain are not so great at communicating with each other and have a mind of their own. Harry’s left hemisphere, usually being active when Harry is in the hamster wheel, likes running for as long as possible. Harry’s right hemisphere, rarely active at all, would like to go to sleep as soon as possible. Together, Harry’s hemispheres will be navigating Harry through the maze of tubes, in each ball deciding which of the outgoing tubes to follow.

Harry’s hemispheres get really tired after making a decision and then need to rest a bit, so they cannot make two decisions in a row. Thus, they make decisions on which tube to take in alternating turns, with the left hemisphere going first. So starting in ball $s$, Harry’s left hemisphere will decide on a tube to follow, ending in some ball $u$, where Harry’s left hemisphere will rest and Harry’s right hemisphere will pick an outgoing tube, et cetera.

Counterintuitively, the hemispheres are familiar with the entire hamster cage and can plan arbitrarily far ahead. Assuming both hemispheres make optimal decisions, how long will it take for Harry to reach his bed? It is guaranteed that each ball has at least one outgoing tube, except the ball containing Harry’s bed which has none (there Harry will rest easily). There are no tubes connecting a ball to itself, but there may be multiple tubes going from one ball to another.

Input

• On the first line are four space-separated integers: the number of plastic balls $1 \leq n \leq 10^5$, the number of tubes $0 \leq m \leq 2 \cdot 10^5$, and the locations of Harry and his bed $0 \leq s, t < n$.

• Then $m$ lines follow, each containing three space-separated integers describing a single tube: the ball in which the tube starts $0 \leq a_ i < n$, in which it ends $0 \leq b_ i < n$ and the time it takes to traverse $1 \leq w_ i \leq 10^4$. Note that each tube can only be traversed in one direction.

Output

Print the time it takes for Harry to reach his bed, or the string infinity if Harry is doomed to roam the tubes forever.

4 5 0 3
0 1 1
1 2 2
2 0 4
2 3 1
2 3 3

11

5 5 0 4
0 1 1
1 2 1
2 3 1
3 0 1
2 4 1

infinity

2 1 0 1
0 1 2

2

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

infinity

3 2 0 1
0 2 3
2 0 3

infinity