Tính phí đường bộ

Vương quốc Byteland có \(N\) nút giao thông trọng điểm được đánh số từ \(1\) đến \(N\). Hệ thống đường cao tốc gồm \(M\) con đường hai chiều đảm bảo đi lại giữa các nút giao thông với nhau, các con đường được đánh số từ \(1\) đến \(M\). Con đường thứ \(i\) nối nút giao thông \(X_i\) với \(Y_i\) (\(1 \le i \le M, 1 \le X_i, Y_i \le N\)) có phí đường bộ là \(Z_i\) (\(Z_i \le 10^6\)).

\begincenter

\endcenter

Ví dụ: Từ nút giao thông 1 đến nút giao thông 4 (như hình vẽ) có hai đường đi khác nhau: đường đi thứ nhất là \(1 \to 2 \to 4\) có tổng phí đường bộ là 30, đường đi thứ hai là \(1 \to 3 \to 4\) có tổng phí đường bộ là 35.

Để giảm chi phí đi lại góp phần thúc đẩy phát triển kinh tế giữa các vùng, Quốc vương đã ban hành chính sách mới cho phép người dân đăng kí miễn phí tối đa \(K\) con đường bất kì trên hành trình của mình.

Yêu cầu: Hãy lập trình tính tổng phí đường bộ nhỏ nhất khi đi từ nút giao thông \(S\) đến nút giao thông \(T\) sau khi được Quốc vương ban hành chính sách mới.

Input

• Dòng đầu ghi năm số nguyên dương \(N, M, K, S, T\).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo ghi ba số nguyên dương \(X_i, Y_i, Z_i\).
• Các số trong tệp cách nhau ít nhất một dấu cách.

Output

• Gồm một số nguyên duy nhất là tổng phí đường bộ nhỏ nhất tìm được.

Example

4 4 1 1 4
1 2 10
1 3 30
2 4 20
3 4 5

5 

Scoring

• Có 20% số điểm tương ứng \(1 < N, M \le 100000\) và \(K = 0\);
• Có 20% số điểm tương ứng \(1 < N \le 100, M \le 1000\) và \(K = 1\);
• Có 20% số điểm tương ứng với \(1 < N, M \le 100000\) và \(K = 1\);
• Có 40% số điểm tương ứng với \(100 < N, M \le 100000\) và \(1 < K \le 10\).