Задача 4<br>ИЗГРАЖДАНЕ НА МРЕЖА

Задача 4<br>ИЗГРАЖДАНЕ НА МРЕЖА

---

Софтуерната фирма Монблан Ложи има нов клиент - компанията Меканикал Мен, специализирана в разработката на роботи. Компанията иска да свърже някои от лабораториите си, да ги наречем бази, със сателитна интернет връзка и след това да свърже с кабел всяка от останалите лаборатории с най-близката база, за да има интернет връзка във всяка лаборатория. За всяка лаборатория са известни координатите й в правоъгълна координатна система и цената за оборудването й като база. Цената за свързване с кабел на две лаборатории е равна на разстоянието между тях. Желанието на Меканикал Мен е цената на разходите за свързване на всички лаборатории с интернет връзка да е колкото се може по-малка.
Като програмист, участвал в различни проекти със сериозни алгоритмични проблеми, на Пиер било възложено да намери решение и за този проект. Той представил едно добро решение. А колко добро може да е вашето?
Напишете програма NET.EXE по зададени координати на лабораториите и цени за оборудване на всяка една от тях като база, намира колкото се може по-малка цена за реализиране на проекта.
Входните данни са зададени в текстов файл NET.INP. Първият ред на входния файл съдържа числото N (3 І N І 500) - броя на лабораториите. Всеки от следващите N реда съдържа по три цели числа: xi, yi и ci. Числата са не по-големи от 1 000 000 000 по абсолютна стойност и са разделени с интервал. Числата xi и yi са координати на съответната лаборатория, а числото ci (0 І ci) е цената за оборудването й като база. Лабораториите са номерирани с числата от 1 до N, съответстващи на реда, по който са зададени във входния файл.
Изходният текстов файл NET.OUT трябва да съдържа два реда. Първият ред съдържа числото M - броя на лабораториите, избрани за бази. Вторият ред съдържа М числа, разделени с интервал - номерата на лабораториите, избрани за бази.
При оценяването на верните решения за всеки тестов пример се взема предвид намерената цена за реализирането на проекта. Състезателят, намерил най-евтино реализиране на проекта, ще получи максималния възможен брой точки за теста. Всеки друг състезател ще получи част от максималния брой в зависимост от намерената цена за реализиране на проекта.

Пример
STAT.INP
3
0 0 10
-1 -1 100
1000 1000 10

STAT.OUT (един възможен изходен файл)
2
1 3

---