Đường kính của một cây được định nghĩa là độ dài đường đi dài nhất của cây đó (theo nghĩa số lượng cạnh trên đường đi). Cho đồ thị vô hướng G = (V, E), với c(e) là trọng số của cạnh e (e ∈ E).

Yêu cầu: Cho một số nguyên dương K, hãy tìm cây khung nhỏ nhất T của G sao cho đường kính của T nhỏ hơn hoặc bằng K.

Dữ liệu vào

Dòng 1: N, M, và K (1 ≤ N ≤ 15, 1 ≤ M ≤ 25)

Dòng i + 1 (i = 1, . . . , M): u, v, và w trong đó w là trọng số của cạnh (u, v)

Kết quả

Ghi ra duy nhất một số là trọng số của cây khung nhỏ nhất tìm được hoặc ghi ra -1 nếu cây khung đó không tồn tại.

Sample Input

6 9 3
1 2 4
1 3 3
1 4 1
2 3 7
2 5 1
3 4 5
3 5 5
3 6 5
5 6 2

Sample Output

16