Đường đi trong đồ thị II

Cho đồ thị có hướng có trọng số $n$ đỉnh và $m$ cạnh. Tìm độ dài đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $n$ có đúng $k$ cạnh.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$, $m$ và $k$.

• $m$ dòng tiếp theo, mỗi dòng chứa ba số $a$, $b$ và $c$ — cạnh từ $a$ đến $b$ có trọng số $c$.

Dữ liệu ra

In độ dài đường đi ngắn nhất. Nếu không có đường đi, in $-1$.

Ràng buộc

• $1\le n\le 100$
• $1\le m\le n(n-1)$
• $1\le k\le {10}^9$
• $1\le c\le {10}^9$

Ví dụ