974. Roads

In a country there are `N` cities connected by `M` one way roads. You can paint any of these roads. To paint a road it costs `D` unit of money where `D` is the length of that road. Your task is to paint some of the roads so that the painted roads can be partitioned into some disjoint cycles such that every vertex appears in exactly `K` of these disjoint cycles. But you have to minimize the costs of painting these roads.

Input starts with a line containing 3 integers `N` (`1\ ≤\ N\ ≤\ 40`), `M` (`1\ ≤\ M\ ≤\ 2000`) and `K` (`1\ ≤\ K`, `1\ ≤\ K*N\ ≤100`). Next lines contain description of `M` roads. Each description contains three integers `s`, `t` (`1\ ≤\ s,\ t\ ≤\ N`, `s\ ≠\ t`) and `D` (`0\ ≤\ D\ <\ 100`). That means there is a road of `D` length from city `s` to city `t`. You can assume that there will be at most one road in one direction between two cities.

Output contains one integer denoting the minimum unit of money needed to paint roads. In the case it is impossible to paint the roads maintaining the constraints output `-1`.

4 8 1
1 2 1  2 1 2  3 4 1  4 3 2
1 3 5  3 1 6  2 4 5  4 2 6

6

4 8 1
1 2 1  2 1 10  3 4 10  4 3 1
1 3 10  3 1 1  2 4 1  4 2 10

4

4 8 2
1 2 1  2 1 2  3 4 1  4 3 2
1 3 5  3 1 6  2 4 5  4 2 6

28

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

-1