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.

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\) cạnh. Các đỉnh được đánh số từ 1 đến \(n\). 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ể.

Chú ý: 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 3 số \(u,v,w\) mô tả cùng 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

• 30%: Đồ thị có dạng một vòng tròn, các đỉnh được trên vòng được sắp xếp từ 1 đến \(n, 1≤n≤100,1≤m≤10000,1≤k≤10^9\).
• 30%: \(1≤n≤100,1≤m≤10000,1≤k≤100.\)
• 40%: \(1≤n≤100,1≤m≤10000,1≤k≤10^9.\)

Example

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

25