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 tinh ~1~ 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ị ~X_i~, ~Y_i~, ~T_i~ 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 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

Giải thích 1

Thiết bị có thể được sử dụng một lần. Để đến hành tinh ~6~ trong thời gian tối thiểu, chúng ta sẽ đi qua kênh ~1 –> 2~ sau đó sẽ dịch chuyển đến hành tinh ~5~ từ đó sẽ đi qua kênh ~5 –> 6~. Chi phí cuối cùng là ~2 + 3~ (dịch chuyển bởi thiết bị) ~ + 9 = 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

Giải thích 2

Thiết bị hoàn toàn không thể sử dụng được. Để đến hành tinh ~6~ từ hành tinh ~1~ trong thời gian tối thiểu, cần đi qua các kênh theo thứ tự ~1 –> 3 –> 4 –> 5 –> 6~ và với thời gian ~5 + 6 + 7 + 9 = 27~ giây.

Hạn chế

• ~1 < N, ≤ 10000, 1 < M ≤ 20000;~
• ~0 ≤ L,K ≤ 10; ~
• ~1 < T_i, P ≤ 100000;~
• ~1 < X_i, 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ó ~T_i = 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~;

Nguồn: Trại đông Bảo Lộc 2021 - thầy Đỗ Phan Thuận