Rar the Cat and his friend go home together on taxi after a party. Rar the Cat lives in a town that can be modelled by a graph with ~V~ nodes and ~E~ bidirectional weighted edges. The party takes place at node ~P~, Rar the Cat's friend lives at node ~D~ and Rar the Cat lives at node ~R~. Rar the Cat decides to send his friend home before going home himself, of course offering to pay for the trip. Below are the fares:
- Flag-down (fixed cost): $3
- Each kilometre for the first 10 kilometres: $2
- Each kilometre after 10 kilometres: $1
Find the minimum cost required to do so, or state that it is impossible.
The first line of input will contain five integers ~V, E, P, D, R~.
The following ~E~ lines will contain three integers ~A, B, C~ on each line, representing an edge connecting two nodes ~A~ and ~B~ with weight ~C~.
If it is not possible for Rar the Cat to send his friend home and then return home, output
If it is possible for Rar the Cat to send his friend home but not possible for him to return home, output the minimum cost required to send his friend home on one line, then output
Yippee!!! on the next line as he would have an excuse to not go home and stay overnight at his friend's place.
If it is possible for Rar the Cat to send his friend home and then return home, output the minimum cost required.
Subtask 1 (100%): ~1 \le V, C \le 100\,000~. ~1 \le E \le 300\,000~. ~0 \le A, B, P, D, R < V~.
Subtask 2 (0%): Sample Testcases.
5 4 0 2 2 0 1 1 1 2 1 2 3 1 3 4 1
5 1 0 1 2 0 1 5
3 1 0 2 1 0 1 1