Cho đồ thị có hướng \(N\) đỉnh và \(M\) cạnh có trọng số không âm. Hãy tìm độ dài của đường đi ngắn thứ \(K\) từ đỉnh \(S\) đến đỉnh \(T\). Các đỉnh hoặc các cạnh có thể đi qua lại nhiều lần trong một đường đi.

Đị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 1000\), \(0 \le M \le 2000\), \(1 \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\), \(1 \le w \le 10^6\)) mô tả cạnh một chiều từ \(u\) sang \(v\) có trọng số \(w\).

Định dạng đầu ra

• Một số nguyên duy nhất là độ dài đường đi ngắn thứ \(K\). Nếu không tồn tại đường đi thứ \(K\), in ra \(-1\).

Ràng buộc

Ví dụ

Input:

3 4 2 1 3
1 2 2
1 3 6
2 3 3
3 2 1

Output:

6

(Giải thích ví dụ: Các đường đi từ 1 đến 3 theo thứ tự độ dài tăng dần là: 1 -> 2 -> 3 (độ dài 5), 1 -> 3 (độ dài 6), 1 -> 2 -> 3 -> 2 -> 3 (độ dài 9)... Đường đi ngắn thứ 2 là 6).