Quay lại vài tiếng trước khi Pusheen đến được nơi tổ chức sự kiện. Pusheen phải vượt qua một chặng đường từ nhà đến nơi tổ chức thông qua các con đường có trong thành phố TA.

Thành phố TA có ~n~ nút giao thông được đánh số từ ~1~ đến ~n~ và ~m~ con đường hai chiều được đánh số từ ~1~ đến ~m~. Trên mỗi con đường này có rất nhiều quán ăn có đồ ăn rất ngon như: bún bò, hủ tiếu, cơm sườn, mì cay, trà sữa,... (người ra đề đã đói bụng khi viết đến đoạn này). Pusheen với sự nổi tiếng ham ăn của mình, đã không thể cưỡng lại được sự hấp dẫn của các hàng quán đó, nên với mỗi con đường, chú sẽ bỏ ra một số tiền nhất định để thưởng thức các món ăn này. Con đường thứ ~i~ kết nối với nút giao thông ~u_i~ với ~v_i~, và Pusheen sẽ phải chi ra chính xác ~c_i~ đơn vị tiền để thưởng thức hết các món ăn.

Tuy nhiên, vì là một người săn sale có kinh nghiệm, Pusheen đã thu thập được ~k~ vé VIP. Với mỗi chiếc vé VIP, Pusheen có thể thưởng thức tất cả các món ăn trên một con đường mà không phải mất tiền.

Biết rằng nhà của Pusheen nằm ở nút giao thông ~s~ và nơi tổ chức sự kiện nằm ở nút giao thông ~t~. Vì còn phải chi tiền cho các mặt hàng hot tại sự kiện, bạn hãy giúp Pusheen tiết kiệm nhiều tiền nhất có thể khi đi từ nhà đến nơi tổ chức nhé!

Input

Dòng đầu tiên ghi năm số nguyên dương ~n, m, k, s, t~ ~(1 \le s, t \le n, s \ne t)~;

~m~ dòng sau, mỗi dòng ghi ba số nguyên ~u_i, v_i, c_i~ ~(1 \le u, v \le n, 1 \le c_i \le 10^6)~.

Output

Một số duy nhất là chi phí ít nhất để Pusheen có thể đi từ nhà đến nơi tổ chức sự kiện.

Dữ liệu vào đảm bảo tồn tại đường đi từ ~s~ đến ~t~.

Giới hạn

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

Sample Input

5 6 1 1 5
1 2 10
2 5 10
1 4 3
3 4 5
3 5 3
1 3 20

Sample Output

3

Giải thích

Bản đồ TA ở ví dụ trên có dạng như sau:

Thành phố có ~5~ nút giao thông, ~6~ tuyến xe buýt và Pusheen cần di từ nút giao thông ~1~ đến nút giao thông ~5~.

Nếu Pusheen không sử vé VIP nào, hành trình ~1 \to 4 \to 3 \to 5~ hết ~11~ đơn vị tiền là đường đi với chi phí ít nhất.

Tuy nhiên, nếu Khuê sử dụng ~1~ vé VIP thì hành trình ~1 \to 3 \to 5~ hết ~3~ đơn vị tiền là ít nhất (vé VIP được sử dụng tại tuyến ~1 \to 3~).