Elon Musk has constructed cities numbered from to on Mars. He initially planned to construct bidirectional roads to connect different cities (where the construction cost of the th road is . One such example for and can be seen below:
However, Mr. Musk changed his mind a bit. Now, he wants to establish countries numbered from to . Then, he will distribute all the cities among these countries following a special rule. After the distribution, Mr. Musk wants to construct some or all of the roads he planned initially in such a way that every pair of cities in each country are connected either directly via a road or through another city. Cities from different countries need not be connected. Mr. Musk will distribute the cities so that the cost of constructing such roads is minimized. One such construction of the example shown above can be seen below (for ):
Now, Mr. Mask has asked you to determine the maximum amount among the cumulative costs of building roads following the rules specified above. In the given example, the maximum cumulative cost is .
Given the configuration of the cities and the number of countries, you need to print the maximum cumulative cost. If such construction is not possible, you need to print .
It is to be noted that it is possible that a country does not have any city in it.
The first line contains three space-separated integers , and which denote the number of cities, countries, and roads, respectively.
Then bidirectional roads will be given in the form of three space-separated integers: , and where and denote the cities at the end of the road and denotes its weight.
Print the maximum among the minimized cumulative costs. If there is no valid answer, print .
Input | Output |
---|---|
7 3 9 1 2 2 1 5 5 1 4 7 2 3 4 3 4 1 4 6 3 0 5 4 0 6 1 5 6 2 | 3 |