Minimum Cost to Buy Ingredients

You are given information about ingredient offerings from various shops. Each offering is represented as a tuple (shop, ingredient, cost). Your task is to choose offerings such that you obtain at least (k) distinct ingredient types with the minimum total cost. If it is impossible to obtain (k) distinct ingredients from the given offerings, output -1.

More formally, you are given three integers (n), (m), and (k) on the first line, where (n) is the number of shops, (m) is the total number of offerings, and (k) is the minimum number of distinct ingredients you must buy. Each of the next (m) lines contains three integers: the shop number, the ingredient type, and the cost of that ingredient. You must select exactly one offering per ingredient type (if chosen) and the sum of the costs for the (k) cheapest distinct ingredient types is the answer.

The problem requires that you compute the minimum sum of costs among all valid selections. If there are fewer than (k) unique ingredient types available, return (-1).

inputFormat

The input is read from standard input and has the following format:

• The first line contains three integers (n), (m), and (k) separated by spaces.
• Each of the next (m) lines contains three integers: the shop number, the ingredient type, and the cost of that ingredient.

All integers are separated by spaces.

outputFormat

Output a single integer to standard output: the minimum total cost to buy at least (k) distinct ingredient types. If it is not possible, output (-1).## sample

4 6 3
0 1 100
0 2 200
1 1 150
1 3 300
2 2 50
3 3 80

230