Đường đi dài nhất qua đúng k cung

Như chúng ta đã biết, bài toán tìm đường đi dài nhất trong một đồ thị có cạnh trọng số không âm là bài toán siêu khó (NP hard). Bài toán sẽ đơn giản hơn nếu như đường đi đó có số cạnh cố định, tức là ta bắt buộc đường đi đó phải đi qua chính xác $k$ cạnh.

Bạn được cho bài toán như sau: Cho một đồ thị có hướng có trọng số gồm $n$ đỉnh và $m$ cung. Các đỉnh được đánh số từ $1$ đến $n$.

Yêu cầu: Tìm một đường đi bất kỳ (bắt đầu tại một đỉnh bất kỳ) đi qua đúng $k$ cung sao cho tổng trọng số các cung được đi qua là lớn nhất có thể.

Một đỉnh hoặc một cung có thể được đi qua nhiều hơn một lần. Đồ thị có thể có khuyên (cung từ một đỉnh tới chính nó) và nhiều cung cùng nối từ $u$ tới $v$.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương $n,m,k$;
• $m$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $u,v,w$ mô tả cung từ $u$ đến $v$ có trọng số $w$.

Dữ liệu ra

Ghi ra một số duy nhất là trọng số lớn nhất tìm được. Nếu không tồn tại đường đi qua đúng $k$ cung thì in ra $-1$.

Ràng buộc

• $1\le n\le 100$, $1\le m\le 10000$, $1\le k\le {10}^9$.
• $1\le u,v\le n$, $0\le w\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): đồ thị có dạng một vòng tròn, các đỉnh trên vòng được sắp xếp từ $1$ đến $n$: $m=n$ và các cung là $1\to 2,2\to 3,\dots ,n-1\to n,n\to 1$ (cho theo thứ tự bất kỳ; khi $n=1$ đó là khuyên $1\to 1$).
• Subtask 2 ($30\%$ số điểm): $k\le 100$.
• Subtask 3 ($40\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ