Harry the Hamster#9885
Harry the Hamster lives in a giant hamster cage. Inside the cage there are plastic balls connected by one-way hamster tubes of various lengths. Harry is currently in ball , and his bed is in ball .
Harry is a simple hamster, and the two halves of his brain do not communicate very well: each has a mind of its own. The left half, usually active when Harry is running in his wheel, wants to keep running for as long as possible. The right half, which is rarely active at all, wants to go to sleep as soon as possible. Together, the two halves guide Harry through the maze of tubes, deciding in each ball which outgoing tube to take.
Making a decision is exhausting, so after each one a brain half needs a short rest and cannot make two decisions in a row. Therefore, the halves take turns choosing a tube, with the left half going first. Starting in ball , the left half chooses a tube, which leads Harry to some ball . There the left half rests while the right half chooses the next outgoing tube, and so on.
Surprisingly, both brain halves know the entire cage and can plan arbitrarily far ahead. Assuming both halves play optimally, how long will it take Harry to reach his bed? It is guaranteed that every ball has at least one outgoing tube, except the ball with Harry's bed, which has none (there Harry can rest peacefully). No tube connects a ball to itself, but there may be several tubes leading from one ball to another.
The first line contains four integers: the number of plastic balls n~(1 \le n \le 10^5), the number of tubes m~(0 \le m \le 2 \cdot 10^5), and the balls and t~(0 \le s, t < n) where Harry and his bed are located.
Each of the next lines contains three integers describing a tube: the ball a_i~(0 \le a_i < n) where the tube starts, the ball b_i~(0 \le b_i < n) where it ends, and the time w_i~(1 \le w_i \le 10^4) needed to traverse it. Each tube can be traversed in one direction only.
Print the time it takes Harry to reach his bed, or the string infinity if Harry is doomed to roam the tubes forever.
Example 1
Example 2
Example 3
Example 4
Example 5