Problem F
Evasion

Powder was hanging out in the Last Drop, when she just heard from Vander that The Last Drop was getting another "random" search for illicit Hex Crystals. She needs to hide all of her Hex Crystals, and fast. However, Powder also left a lot of Hex Crystals in her lab. When the Piltover Enforcers get here and find her missing, they’re surely going to search her lab too. To avoid detection, Powder needs to arrive at her lab from the Last Drop and arrive strictly before the Enforcers, while also making sure to avoid encountering them on the way. Once there, she can grab her crystals and leave instantly. The tunnels are so dark that Powder can’t see the Enforcers coming from ahead. The tunnels are also so narrow that she will be detected if their paths cross through each other at the same time, even if they only meet a single point.

We can represent the tunnel system as an undirected graph, where the $n$ vertices represent junctions and $m$ edges represent tunnels. Powder is currently at The Last Drop, which is located at vertex $s$. Powder’s lab is at vertex $t$, and the Enforcers are currently at vertex $p$. The Enforcers will begin heading directly towards The Last Drop at the exact moment that Powder starts moving. Powder assumes the Enforcers will use some shortest path to get there, but she doesn’t know which one. As soon as the Enforcers arrive at The Last Drop and find Powder missing, they will immediately head for Powder’s lab, again using some shortest path. Powder will be caught if the Enforcers make it to her lab before she does (they will wait there for her to arrive) or if she is in the same position in the graph at the same time as the Enforcers. Note that Powder can be any arbitrarily small, positive distance $\epsilon $ away from the Enforcers without being caught. Powder assumes she will travel at $0.5$ $\mathrm{m}/\mathrm{s}$ and the Enforcers will travel at $1$ $\mathrm{m}/\mathrm{s}$. While the Enforcers will always follow a shortest path to their goal, Powder’s route can be arbitrary, including entering a tunnel without traversing the whole tunnel, or stopping and waiting for an arbitrary amount of time. Powder only considers a route viable if it will succeed regardless of which route the Enforcers choose. Does she have time to make it to her lab, nab the crystals, and evade the Enforcers?

If Powder can get to her lab and grab the crystals before the Enforcers arrive, output the shortest time in which she can do so. It can be shown that for some integer $k$, either the shortest time is exactly $k$ seconds, or Powder cannot finish in $k$ seconds but she can finish in $k + \epsilon $ seconds for any arbitrary small constant $\epsilon > 0$. In either of these cases, output $k$.

If Powder cannot get to her lab before the Enforcers without being caught, output $-1$.

Input

The first line contains five integers, $n$, $m$, $s$, $t$, and $p$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 2 \cdot 10^5$, $1 \leq s, t, p \leq n$), where $n$ is the number of junctions, $m$ is the number of tunnels, $s$ is the location of The Last Drop, $t$ is the location of Powder’s lab, and $p$ is the location where the Enforcers start from. All of $s$, $t$ and $p$ are distinct.
The next $m$ lines each contain three integers, $u$, $v$, and $w$ ($1 \leq u, v \leq n$, $1 \leq w \leq 10^9$). The triple $(u,v,w)$ describes a tunnel from vertex $u$ to vertex $v$ with length $w$ meters. The system of tunnels may not be simple (there may be self-loops or multiple edges).

Output

If Powder can get to her lab and grab the crystals before the Enforcers, output the shortest time that she can do so, in seconds. If Powder cannot get to her lab before the Enforcers without being caught, output $-1$.

3 2 1 2 3
1 2 9
3 1 20

18

3 2 1 2 3
1 2 9
3 1 9

-1

5 4 1 4 5
1 2 200
2 3 1
2 4 100
4 5 400

700