409483: GYM103577 I Impossible problems

Former programming competitors at UNAL are putting together a new contest this year to define which teams will compete in the national finals. This year, they defined $$$n$$$ problem topics and have exactly $$$n$$$ problem setters. Each problem setter has more experience on some topics, so they have collected $$$m$$$ data points about how much time it takes one problem setter to prepare a problem about a given topic. They have been doing this for a while, so they are very creative when they work together. Sometimes, too much. It turns out that a single problem setter can easily prepare problems about various topics, similarly, a problem topic can be prepared by many problem setters. However, when two or more problem setters coincide on a topic, and at least one of them prepares problems about some other topic, they get too creative and will start conflating the topics and they come up with extremely hard problems, which can not be solved within the normal time of official competitions, we can not allow this to happen.

The former UNAL competitors want to prepare the problems spending as little time as possible, so they can go and play with Tomi. That is why they need your help to assign problem setters to topics, in such a way that all topics are covered, and all problem setters work at least with one topic. It is possible that the final problem set has more than one problem per topic. In the example above, if each problem setter chooses a different topic, the time to develop the contest would be 9, whereas if Felipe and Diego share Trees, and Osman chooses Treaps and Math, the total time to develop the contest is 8. Furthermore, if Felipe and Diego choose Trees, Osman and Diego choose Treaps, and Osman chooses Math, they will get too creative and create a problem about Trees, Treaps and Math, which will be very extremely hard.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 200$$$, $$$1 \leq m \leq n^2$$$). The next $$$m$$$ lines, will contain three integers $$$k, t, h$$$ separated by a space, which represents that the problem setter $$$k$$$ needs $$$h$$$ hours to prepare a problem about topic $$$t$$$ ($$$0 \leq k, t < n$$$, $$$1 \leq h \leq 500$$$).

Print a single integer, the minimum total number of hours required to prepare the problem set. Print "Impossible" if it is not possible to develop the problem set with all the topics, with every problem setter working on at least one topic and without problem setters getting too creative.

3 5
0 0 2
1 0 3
1 1 6
2 1 2
2 2 1

8