Vương quốc Flatland có ~n~ thành phố được nối với nhau bởi ~m~ con đường hai chiều. Mỗi con đường nối hai thành phố ~u~ và ~v~, có thời gian ~w~ (tức cần ~w~ đơn vị thời gian để đi hết con đường đó).

Ngoài ra, Flatland còn có ~p~ cổng dịch chuyển ma thuật. Mỗi cổng là một cổng một chiều, cho phép bạn tức thì đi từ một thành phố ~x~ đến thành phố ~y~ mà không tốn thời gian. Tuy nhiên, để tránh lạm dụng ma thuật, bạn chỉ được sử dụng tối đa ~k~ lần cổng dịch chuyển trong toàn bộ hành trình.

Bạn đang ở thành phố ~s~ và muốn đến thành phố ~t~ nhanh nhất có thể, bằng cách kết hợp đi qua các con đường bình thường và sử dụng cổng dịch chuyển.

Hãy tính thời gian ít nhất để từ thành phố ~s~ đến thành phố ~t~, không sử dụng quá ~k~ lần cổng dịch chuyển. Nếu không thể đến được, hãy ghi ra ~-1~.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên: ~n\ m\ p\ k~ (~1 \le n \le 10^5~, ~1 \le m \le 2 \cdot 10^5~, ~0 \le p \le 2 \cdot 10^5~, ~0 \le k \le 20~), là số thành phố, số con đường, số cổng dịch chuyển và số lần sử dụng cổng dịch chuyển tối đa.

• Dòng thứ hai chứa hai số nguyên: ~s\ t~ (~1 \le s, t \le n~), là thành phố xuất phát và thành phố đích.

• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên: ~u\ v\ w~ (~1 \le w \le 10^5~), là con đường hai chiều nối thành phố ~u~ và ~v~ với thời gian ~w~.

• ~p~ dòng tiếp theo, mỗi dòng gồm hai số nguyên: ~x\ y~, là cổng dịch chuyển một chiều từ thành phố ~x~ đến thành phố ~y~.

Dữ liệu ra

• Ghi ra số nguyên duy nhất là thời gian tối thiểu để đi từ ~s~ đến ~t~, sử dụng tối đa ~k~ lần cổng dịch chuyển.
• Nếu không thể đến được, ghi ra ~-1~.

Ví dụ

Đầu ra

5 5 3 1
1 5
1 2 5
2 3 2
3 4 2
4 5 3 
1 3 6
2 4
3 5
1 4

Đầu ra

3

Giải thích

Dùng cổng ~1~ ~4~, rồi đi ~4~ sang ~5~, mất tổng cộng ~3~ đơn vị thời gian.

Tính điểm

• Subtask 1 (~50\%~): ~p = 0, k = 0, n \leq 10^5, m \leq 10^5~.
• Subtask 2 (~30\%~): ~k = 1, n \leq 5*10^4, p \leq 10^5~.
• Subtask 3 (~20\%~): Không có ràng buộc gì thêm.