Khảo cổ

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 (tức là tồn tại một đường đi từ điểm hiện tại đến điểm muốn đến gồm không quá $l$ con đường, không tính trọng số).
   • 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.

Dữ liệu vào

• Dòng $1$: Năm số nguyên $n,m,p,l,k$ $(2\le n\le {10}^4;1\le 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 u,v\le n;u\ne v;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.

Dữ liệu đảm bảo có thể đi từ đỉnh $1$ đến đỉnh $n$ qua các con đường cổ đại.

Dữ liệu ra

In ra 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$).

Ràng buộc

• $2\le n\le {10}^4$, $1\le m\le {10}^4$.
• $0\le l,k\le 10$, $1\le p\le {10}^5$.
• $1\le w\le {10}^5$; không có hai con đường nối cùng một cặp điểm, không có đường nối một điểm với chính nó.
• Có thể đi từ đỉnh $1$ đến đỉnh $n$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $k=0$; $w=1$ với mọi con đường.
• Subtask 2 ($20\%$ số điểm): $k=0$.
• Subtask 3 ($20\%$ số điểm): $n\le 300$.
• Subtask 4 ($30\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ