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)~.

Ví dụ: Từ nút giao thông ~1~ đến nút giao thông ~4~ có hai đường đi khác nhau: đường đi thứ nhất là ~1 \rightarrow 2 \rightarrow 4~ có tổng phí đường bộ là ~30~, đường đi thứ hai là ~1 \rightarrow 3 \rightarrow 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

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

Scoring

Sample Input 1

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

Sample Output 1

5

Notes

Chọn miễn phí con đường thứ ~2~, khi đó hành trình là ~1 \rightarrow 3 \rightarrow 4~ có tổng phí là: ~0 + 5~.