eolymp
bolt
Try our new interface for solving problems
Problems

Cities - competitors (RU)

Cities - competitors (RU)

Time limit 2 seconds
Memory limit 64 MiB

В стране Флатландии имеется N городов, каждый город выпускает один определенный товар из M товаров. Города, выпускающие один и тот же товар, являются городами-конкурентами. Города Флатландии хотят объединиться в торговую сеть. Как показали исследования, для того, чтобы какие-то города могли объединиться в торговую сеть, необходимо и достаточно, чтобы из любого города A можно было добраться по дорогам сети в любой другой город B. Причем, в такой сети не должно быть дорог между городами-конкурентами, т.е. города-конкуренты не являются соседями в этой сети.

Ваша задача - по заданным городам Флатландии построить сеть дорог таким образом, чтобы длина сети была минимальной. Длина сети есть сумма длин построенных дорог. Дороги между городами строятся таким образом, чтобы попасть на них можно было только из городов, которые они соединяют. Для того чтобы избежать пересечений, дороги можно располагать на разных уровнях.

Input data

В первой строке входного файла записаны через пробел два целых числа N и M (1N200, 1M200). В последующих N строках описаны города Флатландии, описание каждого города занимает одну строку. В соответствующей строке записаны через пробел три целых числа X_i, Y_i, Z_i, где X_i и Y_i - координаты i-го города, a Z_i - номер продукции, которую выпускает этот город (-10000 X_i, Y_i10000, 1Z_iM, 1iN).

Output data

В первую строку выходного файла необходимо вывести одно вещественное число с точностью до 0.001 - минимальную длину сети дорог. Если города объединить в торговую сеть невозможно, то вывести -1.

Examples

Input example #1
8 3
3 3 1
3 10 1
5 6 2
10 6 3
10 10 2
15 3 1
15 6 3
15 10 2
Output example #1
29.909