Đồ thị có hướng gồm \(N\) đỉnh và \(M\) cạnh có trọng số không âm. An muốn tìm đường đi từ đỉnh \(S\) đến đỉnh \(T\).

Tuy nhiên, luật giao thông đặc biệt cho phép An đi ngược chiều tối đa \(K\) con đường một chiều trên hành trình của mình với chi phí đi ngược chiều bằng chính chi phí của con đường đó.

Hãy tìm chi phí tối thiểu để An đi từ \(S\) đến \(T\).

Định dạng đầu vào

• Dòng đầu chứa năm số nguyên \(N, M, K, S, T\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\), \(0 \le K \le 5\), \(1 \le S, T \le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N\), \(1 \le w \le 10^9\)) mô tả con đường một chiều nối từ \(u\) sang \(v\) có độ dài là \(w\).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí tối thiểu. Nếu không thể đi tới, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

4 4 1 1 4
1 2 2
3 2 1
3 4 5
1 4 10

Output:

8

(Giải thích ví dụ: Đi 1 -> 2, rồi đi ngược chiều 3 -> 2 thành 2 -> 3 (tốn chi phí 1), rồi đi 3 -> 4 (chi phí 5). Tổng chi phí: 2 + 1 + 5 = 8. Nếu đi 1 -> 4 trực tiếp tốn 10).