Summer Institute @ University of Central Florida: Contest 1, Problem 1

An ant dynasty has decided to move into a giant ant hill consisting of ~n~ burrows. The dynasty has a complicated social structure formed by a coalition of ~k~ ant clans, where each clan doesn't get along well with the others. To keep the peace, the ant emperor wants to partition all ~n~ burrows into ~k~ equally-sized districts (one per clan), so that no ant from any clan should be able to reach any ant of an opposing clan. After deciding on the districts, the ants will drill tunnels between certain carefully chosen pairs of burrows so ants in each clan can travel among all the burrows allocated to the district for the clan. The ant emperor would like to know the cheapest cost possible for forming his districts and building the resulting tunnels.

Input Specification

The first line of input contains 3 space separated integers: ~n~ ~(1 \le n \le 20)~, ~m~ ~(1 \le m \le \frac{n(n-1)}{2})~ and ~k~ ~(1 \le k \le n)~, representing the number of burrows, number of possible tunnels that can be drilled, and the number of districts to form. Burrows are labeled with identifiers ~[1, n]~.

This is followed by ~m~ lines each containing 3 space separated integers: ~i~ ~(1 \le i \le n)~, ~j~ ~(1 \le j \le n, i \neq j)~, and ~c~ ~(1 \le c \le 300)~ meaning that the burrow labeled ~i~ can be connected by a tunnel to the burrow labeled ~j~ with cost ~c~.

Output Specification

On a line by itself, print the minimum cost possible of the desired partition, or -1 if such a district plan is impossible.

Sample Input 1

4 4 2
1 2 300
2 3 200
3 4 100
4 1 8

Sample Output 1

208

Sample Input 2

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

Sample Output 2

-1