Vé xe miễn phí

Tham gia trò chơi nhảy lò cò, thật may mắn, Khuê đã giành giải nhất của cuộc thi. Phần thưởng mà Khuê nhận được là $k$ vé xe buýt miễn phí để đi thăm quan thành phố Hạ Long. Mỗi vé xe chỉ được sử dụng một lần và có thể sử dụng cho bất kỳ tuyến xe buýt nào trong thành phố. Thành phố có $n$ nút giao thông được đánh số từ $1$ đến $n$ và $m$ tuyến xe buýt hai chiều. Mỗi cặp nút giao thông $i,j$ có không quá một tuyến xe buýt hai chiều, nếu có thì để đi từ nút $i$ đến nút $j$ (hoặc từ nút $j$ đến nút $i$) với giá vé là $c_{ij}=c_{ji}$ đồng. Xuất phát từ nút giao thông $s$, Khuê muốn di chuyển đến nút giao thông $t$ và anh luôn lựa chọn đường đi với chi phí ít nhất.

Ví dụ: thành phố có $5$ nút giao thông và $6$ tuyến xe buýt:

• Tuyến 1: $1-2$ giá vé $10$ đồng; Tuyến 2: $2-5$ giá vé $10$ đồng;
• Tuyến 3: $1-4$ giá vé $3$ đồng; Tuyến 4: $3-4$ giá vé $5$ đồng;
• Tuyến 5: $3-5$ giá vé $3$ đồng; Tuyến 6: $1-3$ giá vé $20$ đồng.

Xuất phát từ nút $1$ đến nút $5$, đi theo hành trình $1\to 4\to 3\to 5$ hết $11$ đồng là đường đi với chi phí ít nhất. Tuy nhiên, nếu Khuê sử dụng $1$ vé xe miễn phí thì đường đi $1\to 3\to 5$ hết $3$ đồng là ít nhất (vé xe miễn phí được sử dụng tại tuyến $1-3$).

Yêu cầu: Cho biết các tuyến xe buýt với giá vé tương ứng và các giá trị $s,t,k$. Hãy tính chi phí ít nhất để đi từ nút giao thông $s$ đến nút giao thông $t$ mà không sử dụng quá $k$ vé xe miễn phí. Mỗi lần đi qua một tuyến xe buýt, Khuê hoặc trả đúng giá vé của tuyến đó, hoặc dùng một vé xe miễn phí (khi đó lần đi này không mất tiền).

Dữ liệu vào

• Dòng đầu tiên ghi năm số nguyên dương $n,m,k,s,t$;
• $m$ dòng sau, mỗi dòng $3$ số nguyên $i,j,c_{ij}$ mô tả có tuyến xe buýt $i-j$ hết $c_{ij}$ đồng.

Dữ liệu ra

Một số duy nhất là chi phí ít nhất để đi từ nút giao thông $s$ đến nút giao thông $t$ mà không sử dụng quá $k$ vé xe miễn phí.

Ràng buộc

• $2\le n\le {10}^5$, $1\le m\le {10}^5$, $1\le k\le 5$.
• $1\le s,t\le n$, $s\ne t$.
• $1\le i,j\le n$, $i\ne j$; mỗi cặp nút có không quá một tuyến xe buýt.
• $1\le c_{ij}\le {10}^9$.
• Dữ liệu đảm bảo có thể đi từ nút $s$ đến nút $t$.

Subtasks

• Có $40\%$ số test ứng với $40\%$ số điểm có $n\le 100$, $m\le 1000$ và $k=1$;
• Có $20\%$ số test ứng với $20\%$ số điểm có $n\le {10}^5$, $m\le {10}^5$ và $k=1$;
• Có $40\%$ số test còn lại ứng với $40\%$ số điểm có $n\le {10}^5$, $m\le {10}^5$ và $k\le 5$.

Ví dụ