Cities - Competitors#174
In Flatlandia, there are cities. Each city sells exactly one of possible goods. Cities selling the same good are called competitor cities. The goal is to connect all the cities with a trade network that satisfies the following:
It is possible to get from any city to any other city using the roads of the network (the network is connected).
There is no direct road between competitor cities; that is, competitor cities cannot be neighbors in the network.
Your task is to design such a road network so that its total length is minimized. The length of the network is defined as the sum of the lengths of all constructed roads. Roads can only be accessed from the two cities they connect, and they may be built at different levels to avoid intersections.
The first line contains two integers and (1 \leq N \leq 200, 1 \leq M \leq 200). Each of the next lines contains three integers X_i, Y_i, Z_i: X_i and Y_i are the coordinates of city , and Z_i is the number of the good sold in this city (-10000 \leq X_i, Y_i \leq 10000, 1 \leq Z_i \leq M, 1 \leq i \leq N).
Print one real number with precision — the minimum possible total length of the road network. If it is not possible to connect all cities into such a network, print -1.
Example 1