Cities - Competitors
In the country of Flatland, there are N cities, each specializing in the production of one specific product out of M possible products. Cities that produce the same product are considered competitors. The goal is to form a trade network that connects all cities. Research indicates that for a successful trade network, it must be possible to travel from any city A to any other city B using the network's roads. Importantly, no roads should connect competitor cities directly, meaning these cities cannot be neighbors in the network.
Your task is to design a road network for these cities such that the total length of the network is minimized. The length of the network is defined as the sum of the lengths of all constructed roads. Roads are constructed to be accessible only from the cities they connect, and they can be built on different levels to avoid intersections.
Input
The first line of the input contains two integers N and M (1 ≤ N ≤ 200, 1 ≤ M ≤ 200). The next N lines provide details about each city in Flatland, with each line containing three integers X_i, Y_i, Z_i. Here, X_i and Y_i are the coordinates of the i-th city, and Z_i is the product number produced by this city (-10000 ≤ X_i, Y_i ≤ 10000, 1 ≤ Z_i ≤ M, 1 ≤ i ≤ N).
Output
The first line of the output should contain a single real number with a precision of 0.001 - representing the minimal length of the road network. If it is impossible to connect all cities into a trade network, output -1.