Cho một đồ thị đơn giản gồm $N$ đỉnh được đánh số từ $1$ đến $N$ và $M$ cạnh vô hướng có trọng số.

Khi di chuyển giữa hai đỉnh bằng một cạnh, thời gian tiêu tốn bằng trọng số của cạnh đó. Ví dụ, nếu sử dụng một cạnh có trọng số là 3, bạn sẽ mất 3 giờ để di chuyển. Trong khi di chuyển, bạn không ở tại bất kỳ đỉnh nào. Bạn cũng có thể chọn đứng yên tại một đỉnh để chờ đợi mà không cần sử dụng cạnh.

Bạn cần di chuyển từ đỉnh $1$ qua đỉnh $K$ rồi đến đỉnh $N$ trong thời gian ngắn nhất có thể.

Bạn được phép thực hiện hành động "hồi quy" tối đa $1$ lần như sau:

• Di chuyển đến đỉnh mà bạn đã ở đó vào thời điểm $T$ giờ trước. Bạn phải đang ở trên một đỉnh trước và sau khi thực hiện hành động này. Bạn không thể thực hiện hành động này nếu chưa trôi qua $T$ giờ kể từ khi xuất phát.

Hãy tìm thời gian tối thiểu để di chuyển từ đỉnh $1$ qua đỉnh $K$ rồi đến đỉnh $N$ khi được phép sử dụng hành động hồi quy tối đa $1$ lần.

Dữ liệu vào

Dòng đầu tiên chứa số đỉnh $N$, số cạnh $M$, đỉnh trung gian $K$ và thời gian $T$, cách nhau bởi dấu cách. $(3 \le N \le 10^5;$ $0 \le M \le 10^5;$ $2 \le K \le N-1;$ $1 \le T \le 10^9)$

Từ dòng thứ hai trở đi, mỗi dòng trong số $M$ dòng chứa hai đỉnh $u, v$ và trọng số $c$ của cạnh nối giữa chúng, cách nhau bởi dấu cách. $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

Dữ liệu ra

Dòng đầu tiên in ra thời gian tối thiểu để di chuyển từ đỉnh $1$ qua đỉnh $K$ rồi đến đỉnh $N$. Nếu không thể thực hiện hành trình này, hãy in ra -1.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6

Dữ liệu vào 2

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

Dữ liệu ra 2

-1