Bạn là một nhà khảo cổ học đang thực hiện một cuộc khảo sát trên một hòn đảo cổ xưa, nơi có nhiều khu vực khảo cổ khác nhau được kết nối bằng những con đường cổ đại. Bản đồ hòn đảo gồm ~n~ điểm khảo cổ, đánh số từ ~1~ đến ~n~ và ~m~ con đường cổ đại hai chiều, đường cổ đại thứ ~i~ nối trực tiếp từ điểm khảo cổ ~u_i~ đến điểm khảo cổ ~v_i~. Bạn cần di chuyển từ một điểm khảo cổ chính (đỉnh ~1~) đến điểm khảo cổ quan trọng nhất (đỉnh ~n~).

Để thuận tiện, bạn có hai phương án di chuyển:

1. Di chuyển qua các con đường cổ đại: Mỗi con đường cổ đại có một chi phí di chuyển nhất định được cho bởi trọng số của cạnh nối hai điểm khảo cổ.
2. Sử dụng cổng di chuyển: Bạn có thể sử dụng một loại cổng di chuyển ma thuật để di chuyển trực tiếp từ một điểm khảo cổ này đến một điểm khảo cổ khác. Cổng di chuyển ma thuật có một số hạn chế:
   • Bạn chỉ có thể sử dụng cổng di chuyển ma thuật nếu khu vực khảo cổ bạn muốn đến có thể được tiếp cận từ khu vực khảo cổ hiện tại thông qua không quá ~l~ con đường cổ đại.
   • Mỗi lần sử dụng cổng di chuyển ma thuật tốn một chi phí cố định ~p~.
   • Bạn chỉ được phép sử dụng cổng di chuyển ma thuật không quá ~k~ lần.

Yêu cầu: Tìm cách di chuyển từ điểm khảo cổ chính (đỉnh ~1~) đến điểm khảo cổ quan trọng nhất (đỉnh ~n~) sao cho tổng chi phí di chuyển là nhỏ nhất.

Input

• Dòng 1: Năm số nguyên ~n, m, p, l, k~ ~(1 < n, m \le 10^4; 0 \le l, k \le 10; 1 \le p \le 10^5)~.
• Dòng ~2 \dots m+1~: Mỗi dòng ba số nguyên ~u, v, w~ ~(1 \le w \le 10^5)~ biểu thị một con đường cổ đại nối hai điểm khảo cổ ~u~ và ~v~ với trọng số ~w~. Mỗi cặp điểm khảo cổ ~u~ và ~v~ chỉ có một con đường cổ đại duy nhất nối trực tiếp.

Output

Chứa một số nguyên là tổng chi phí di chuyển nhỏ nhất từ điểm khảo cổ chính (đỉnh ~1~) đến điểm khảo cổ quan trọng (đỉnh ~n~).

Scoring

Sample Input 1

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 1

14

Sample Input 2

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 2

27

Notes

• Ví dụ 1: Đường đi có tổng chi phí nhỏ nhất là ~1-3-4-6~, có tổng trọng số ~5+6+3=14~, trong đó có sử dụng một cổng di chuyển ma thuật nối từ địa điểm ~4~ đến địa điểm ~6~.
• Ví dụ 2: Đường đi có tổng chi phí nhỏ nhất là ~1-3-4-5-6~, có tổng trọng số ~5+6+7+9=27~.