题目描述

小明所在的快递公司在运送某批特殊货物时，遇到一项额外需求： 货物需要先去指定的中转点(可能要取某些材料，或者中途加固包装)再送到最终目的地。换言之，快递员必须从”仓库“出发到达“客户地点”经过一个特定的”中转点“。现给你一张城市道路网的信息，请帮小明规划一条最短行驶时间的路线：从起点$S$出发必须经过指定中转点$H$,再到达终点$T$。

给定一个城市道路网，共有 $n$个送货点(编号：$1\le i \le n$)，以及 $m$ 条双向道路。每条道路连接两个不同的送货点，并具有正整数的 行驶时间。现指定三个特殊节点： $S$表示起始送货点(往往是仓库所在位置)； $T$表示目标送货点(客户所在位置)； $H$ 表示中转点(必须经过，用于中途取件或特殊检查) 请你计算一条从$S$ 出发、必经$H$、最终到达$T$的最短行驶时间。如果无法到达或无法满足必须经过$H$ 的要求，则输出 -1。

所有道路均为双向，行驶时间相同。不存在重边和自环(即任意一对送货点之间至多存在一条直接道路，且不会有连到自身的道路)。若有多种方案均满足“从 $S$出发、经过 $H$、到达 $T$”的要求，则输出行驶时间最小的那条线路所需的时间。

输入格式

第一行包含四个整数$n$($2\le n \le 10^5$)，$m$($1\le m \le 2*10^5$)，$S$($1\le S \le n$)，$T$($1\le T \le n$),分别表示：送货点数量，道路数量，起点编号和终点编号

第二行包含一个$H$($1\le H \le n$，且$H \neq S$)，表示必须经过的中转点编号

接下来$m$行，每行包含三个整数$u$，$v$，$w$，表示再编号$u$，$v$($1\le u,v \le n$，且$u \neq v$)之间有一条双向道路，行驶时间为$w$($1\le w \le 10^9$)

输出格式

输出一个整数，从起点到终点的最短的行驶时间。

样例

输入

6 7 1 6
4
1 2 7
1 3 9
2 4 8
2 5 3
3 4 2
4 6 4
5 6 10

输出

15