Như chúng ta đã biết, bài toán tìm đường đi nào đó 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.

Cho một đồ thị có hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh. 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.

Input

• 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ố ~u,v,w~ mô tả cung từ ~u~ đến ~v~ có trọng số ~w~.

Output

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~.

Scoring

Sample Input 1

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

Sample Output 1

25