Powder 正在 The Last Drop 中闲逛，这时她刚从 Vander 那里听说 The Last Drop 即将迎来又一次针对非法海克斯水晶（Hex Crystals）的“例行”搜查。她需要快速藏好她所有的海克斯水晶。然而，Powder 还在她的实验室里留了许多海克斯水晶。当皮尔特沃夫执法官（Piltover Enforcers）到达这里并发现她失踪时，他们肯定也会去搜查她的实验室。为了避免被发现，Powder 需要从 The Last Drop 出发前往她的实验室，并且必须在执法官到达之前严格提前到达，同时还要确保在途中避免与他们相遇。一旦到达实验室，她就可以立即拿走水晶并离开。隧道里非常黑暗，以至于 Powder 无法看到从前方走来的执法官。隧道也非常狭窄，如果他们的路径在同一时间发生交叠，即使他们只是在单点相遇，她也会被发现。

我们可以将隧道系统表示为一个无向图，其中 $n$ 个顶点代表路口，$m$ 条边代表隧道。Powder 目前位于 The Last Drop，对应顶点 $s$。Powder 的实验室位于顶点 $t$，而执法官目前位于顶点 $p$。在 Powder 开始移动的同一瞬间，执法官将开始直接前往 The Last Drop。Powder 假设执法官会选择某条最短路径前往那里，但她不知道具体是哪一条。一旦执法官到达 The Last Drop 并发现 Powder 不在，他们会立即前往 Powder 的实验室，同样会选择某条最短路径。如果执法官在 Powder 之前到达她的实验室（他们会在那里等她出现），或者如果她在同一时间与执法官处于图中的相同位置，Powder 就会被抓住。注意，Powder 只要与执法官保持任意小的正距离 $\epsilon$，就不会被抓住。Powder 假设自己的移动速度为 $0.5 \text{ m/s}$，而执法官的移动速度为 $1 \text{ m/s}$。虽然执法官总是会沿着前往目标的最短路径行进，但 Powder 的路线可以是任意的，包括进入一条隧道而不走完整个隧道，或者停下来等待任意长的时间。Powder 仅在一条路线无论执法官选择哪条路线都能成功时，才认为该路线是可行的。她是否有足够的时间到达实验室、拿走水晶并避开执法官？

如果 Powder 能够在执法官到达之前到达实验室并拿走水晶，输出她能做到这一点的最短时间。可以证明，对于某个整数 $k$，最短时间要么恰好是 $k$ 秒，要么 Powder 无法在 $k$ 秒内完成，但对于任意小的常数 $\epsilon > 0$，她可以在 $k + \epsilon$ 秒内完成。在这两种情况下，均输出 $k$。

如果 Powder 无法在不被抓住的情况下在执法官之前到达实验室，输出 $-1$。

输入格式

第一行包含五个整数 $n, m, s, t$ 和 $p$（$1 \le n \le 10^5$，$1 \le m \le 2 \cdot 10^5$，$1 \le s, t, p \le n$），其中 $n$ 是路口数量，$m$ 是隧道数量，$s$ 是 The Last Drop 的位置，$t$ 是 Powder 实验室的位置，$p$ 是执法官出发的位置。$s, t$ 和 $p$ 两两不同。

接下来的 $m$ 行，每行包含三个整数 $u, v$ 和 $w$（$1 \le u, v \le n$，$1 \le w \le 10^9$）。三元组 $(u, v, w)$ 描述了一条连接顶点 $u$ 和顶点 $v$ 且长度为 $w$ 米的隧道。隧道系统可能不是简单图（可能存在自环或重边）。

输出格式

如果 Powder 能够在执法官到达之前到达实验室并拿走水晶，输出她能做到这一点的最短时间（以秒为单位）。如果 Powder 无法在不被抓住的情况下在执法官之前到达实验室，输出 $-1$。

样例

输入样例 1

3 2 1 2 3
1 2 9
3 1 20

输出样例 1

18

输入样例 2

3 2 1 2 3
1 2 9
3 1 9

输出样例 2

-1

输入样例 3

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

输出样例 3

700