There is a simple graph consisting of $N$ vertices, numbered from $1$ to $N$, and $M$ undirected weighted edges.

Moving between two vertices using an edge takes time equal to the weight of the edge. For example, it takes 3 hours to move between two vertices using an edge with a weight of 3. While moving, you are not at any vertex. You can also spend time staying at a vertex without using any edges.

You must travel from vertex $1$ to vertex $N$ passing through vertex $K$ as quickly as possible.

You can perform the following "regression" action at most once:

• Move to the vertex where you were $T$ hours ago. You must be at a vertex both before and after the move. You cannot perform this action if $T$ hours have not yet passed since you started.

Find the minimum time required to travel from vertex $1$ to vertex $N$ passing through vertex $K$ when you can use the regression action at most once.

Input

The first line contains the number of vertices $N$, the number of edges $M$, the vertex $K$ that must be visited, and $T$, separated by spaces. $(3 \le N \le 10^5;$ $0 \le M \le 10^5;$ $2 \le K \le N-1;$ $1 \le T \le 10^9)$

From the second line, $M$ lines follow, each containing the two vertices $u$ and $v$ connected by an edge, and the weight $c$, separated by spaces. $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

Output

Output the minimum time required to travel from vertex $1$ to vertex $N$ passing through vertex $K$ on the first line. If such a trip is impossible, output -1 instead.

Examples

Input 1

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

Output 1

6

Input 2

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

Output 2

-1