有一个包含 $N$ 个顶点（编号从 $1$ 到 $N$）和 $M$ 条无向加权边的简单图。

通过边在两个顶点之间移动需要花费与边权重相等的时间。例如，通过权重为 $3$ 的边在两个顶点间移动需要 $3$ 小时。在移动过程中，你不会处于任何顶点上。你也可以选择停留在顶点上不动来消耗时间。

你需要从顶点 $1$ 出发，经过顶点 $K$，最终到达顶点 $N$，并尽可能快地完成这一过程。

你可以执行最多 $1$ 次以下“回溯”操作：

• 回到 $T$ 小时前所在的顶点。执行此操作前后，你都必须处于某个顶点上。如果你出发的时间还不到 $T$ 小时，则无法执行此操作。

请计算在最多使用 $1$ 次回溯操作的情况下，从顶点 $1$ 出发，经过顶点 $K$ 到达顶点 $N$ 所需的最短时间。

输入格式

第一行包含四个由空格分隔的整数，分别为简单图的顶点数 $N$、边数 $M$、必须经过的顶点编号 $K$ 以及时间 $T$。 $(3 \le N \le 10^5;$ $0 \le M \le 10^5;$ $2 \le K \le N-1;$ $1 \le T \le 10^9)$

接下来的 $M$ 行，每行包含三个由空格分隔的整数 $u$、$v$ 和 $c$，表示连接顶点 $u$ 和 $v$ 的边，其权重为 $c$。 $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

输出格式

第一行输出从顶点 $1$ 出发，经过顶点 $K$ 到达顶点 $N$ 所需的最短时间。 如果无法完成此路径，则输出 -1。

样例

输入 1

4 3 3 1
1 2 2
2 3 1
2 4 3

输出 1

6

输入 2

4 3 2 0
1 2 1
2 3 2
3 1 3

输出 2

-1