eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Города - конкуренты

Города - конкуренты

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

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

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

Входные данные

В первой строке входного файла записаны через пробел два целых числа N и M (1 ≤ N ≤ 200, 1 ≤ M ≤ 200). В последующих N строках описаны города Флатландии, описание каждого города занимает одну строку. В соответствующей строке записаны через пробел три целых числа X[i], Y[i], Z[i], где X[i] и Y[i] - координаты i-го города, a Z[i] - номер продукции, которую выпускает этот город (-10000 ≤ X[i], Y[i] ≤ 10000, 1 ≤ Z[i] ≤ M, 1 ≤ i ≤ N).

Выходные данные

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

Пример

Входные данные #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
Выходные данные #1
29.909