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

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

Ràng buộc