Cô kỹ sư Alice đang sống ở trong thiên hà VNOI2020. Trong thiên hà này có N hành tinh khác nhau và M kênh vận chuyển hai chiều dạng (x, y, t) cho phép bạn di chuyển từ hành tinh x đến hành tinh y (hoặc ngược lại) trong t giây. Nhưng Alice nhận thấy phương pháp vận chuyển này rất kém hiệu quả nên đã phát triển một thiết bị cho phép bạn dịch chuyển từ hành tinh x đến bất kỳ hành tinh y nào khác trong P giây với điều kiện bạn có thể đến hành tinh y đó từ hành tinh x chỉ sử dụng tối đa L kênh vận chuyển. Thiết bị này hiện mới là bản thử nghiệm nên không thể được sử dụng quá K lần. Alice đang ở hành tinh1 và muốn biết thời gian tối thiểu để đến hành tinh N.

Yêu cầu: Viết chương trình tính thời gian tối thiểu cần thiết để đến được hành tinh N bắt đầu từ hành tinh 1.

Dữ liệu vào

Dòng đầu tiên chứa 5 giá trị N, M, P, L, K cách nhau một dấu cách.

Mỗi dòng trong số M dòng sau chứa 3 giá trị Xi, Yi, Ti mô tả một kênh vận chuyển. Dữ liệu đảm bảo có nhiều nhất một kênh giữa hai hành tinh.

Kết quả

Kết quả ghi ra một giá trị duy nhất là thời gian tối thiểu cần thiết để đến hành tinh N bắt đầu từ hành tinh 1. Dữ liệu đảm bảo luôn có đáp án.

Sample Input

6 7 3 2 1
1 2 2
1 3 5
2 3 4
2 4 23
3 4 6
5 4 7
5 6 9

Sample Output

14

Sample Input

6 7 3 2 0
1 2 2
1 3 5
2 3 4
2 4 23
3 4 6
5 4 7
5 6 9

Sample Output

27

Hạn chế

ˆ 1 < N, ≤ 10000, 1 < M ≤ 20000;
ˆ 0 ≤ L, K ≤ 10;
ˆ 1 < T i, P ≤ 100000;
     1 < Xi, Y i ≤ N;
ˆ 24% số điểm ứng với các test có K = 0 và tất cả các kênh vận chuyển đều có Ti = 1;
ˆ 16% số điểm ứng với các test khác có K = 0;
ˆ 16% số điểm ứng với các test khác đảm bảo N ≤ 300;