$1$번부터 $N$번까지 번호가 매겨진 $N$개의 정점과 $M$개의 무향 가중치 간선으로 이루어진 단순 그래프가 있다.

간선을 이용하여 두 정점을 이동할 때에는 간선의 가중치 시간이 걸린다. 예를 들어, 가중치가 3인 간선을 이용하여 두 정점을 이동할 때는 3시간이 걸린다. 이동하는 중에는 어떠한 정점에도 있지 않다. 간선을 이용하지 않고 정점에서 가만히 있으면서 시간을 보낼 수도 있다.

당신은 $1$번 정점에서 출발해서 $K$번 정점을 거쳐 $N$번 정점으로 최대한 빨리 이동해야 한다.

당신은 다음과 같은 회귀 행동을 최대 $1$번 할 수 있다.

• $T$시간 전에 있던 정점으로 이동한다. 이동하기 전과 후 모두 정점 위에 있어야 한다. 출발한 지 $T$시간이 지나지 않았다면 이 행동을 할 수 없다.

회귀 행동을 최대 $1$번 사용할 수 있을 때 $1$번 정점에서 출발해서 $K$번 정점을 거쳐 $N$번 정점으로 이동하는 데 걸리는 최소 시간을 구하시오.

Input

첫 번째 줄에 단순 그래프의 정점의 개수 $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$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

Output

첫 번째 줄에 $1$번 정점에서 출발해서 $K$번 정점을 거쳐 $N$번 정점으로 이동하는 데 걸리는 최소 시간을 출력한다. 단, 이러한 이동이 불가능한 경우 -1을 대신 출력한다.

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