In a country there are n cities con- nected 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 ap- pears in exactly k of these disjoint cycles. But you have to minimize the costs of painting these roads. Input First line of the input contains T the number of test case. Then fol- lowing lines contains T Test cases. Each case starts with a line containing 3 integers n (1 ≤ n ≤ 40), m (1 ≤ m ≤ 2000) and k (1 ≤ k and 1 ≤ k ∗ n ≤ 100). Next m lines contain description of m roads. Each line contains three integers f, t (0 ≤ f,t < n and f ̸= t) and d (0 ≤ d < 100). That means there is a road of d length from city f to city t. You can assume that there will be at most one road in one direction between two cities. Output For each test case output contains 1 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’. Sample Input 4 481 011 102 231 322 025 206 135 316 481 011 1 0 10 2 3 10
2/2 321 0 2 10 201 131 3 1 10 482 011 102 231 322 025 206 135 316 341 015 106 027 208 Sample Output 6 4 28 -1