Một phi thuyền không gian cần bay từ hành tinh \(S\) đến hành tinh \(T\) qua một hệ thống cổng dịch chuyển một chiều gồm \(N\) hành tinh và \(M\) con đường. Mỗi con đường đi qua có một lượng năng lượng tiêu thụ hoặc bổ sung nhất định (trọng số âm).

Tuy nhiên, việc đi qua cổng bổ sung năng lượng (trọng số âm) gây ra áp lực rất lớn lên động cơ phi thuyền. Hãy tìm đường đi có tổng chi phí năng lượng tiêu thụ là nhỏ nhất từ \(S\) đến \(T\) sao cho số lần phi thuyền đi qua các con đường mang trọng số âm không vượt quá \(K\).

Dữ liệu vào

• Dòng đầu tiên chứa năm số nguyên \(N, M, K, S\) và \(T\) (\(1 \le N \le 1000\), \(1 \le M \le 4000\), \(0 \le K \le 10\), \(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\), \(-1000 \le w \le 1000\)) mô tả một con đường một chiều đi từ \(u\) đến \(v\) có trọng số \(w\).

Kết quả ra

• In ra một số nguyên duy nhất là chi phí năng lượng tiêu thụ nhỏ nhất thỏa mãn yêu cầu. Nếu không thể đi từ \(S\) đến \(T\) thỏa mãn điều kiện, in ra \(-1\).

Ví dụ

Input

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

Output

3