Локальні мережі#11644
У великій ІТ-компанії є комп'ютерів (1 \le N \le 1000). Ці комп'ютери потрібно об'єднати у локальну мережу або, якщо це неможливо – у декілька локальних мереж. Під локальною мережею мається на увазі система пов'язаних між собою комп'ютерів, у тому числі через проміжні комп'ютери. Керівництво компанії хоче прорахувати, мінімальну та максимально можливі вартості об'єднання комп'ютерів у мережу.
Завдання 1. Визначте максимальну вартість об'єднання комп'ютерів у локальну мережу, коли будуть задіяні усі можливі зв'язки між комп'ютерами. Якщо усі комп'ютери не можна поєднати в одну мережу (щоб між будь-якою парою комп'ютерів був зв'язок, у тому числі через проміжні комп'ютери), то побудуйте дві чи декілька локальних мереж, які не пов'язані між собою, але так, щоб були задіяні усі можливі зв'язки між комп'ютерами, які вказані у вхідних даних.
Завдання 2. Для побудованої в завданні 1 локальної мережі (або локальних мереж) визначте мінімальну вартість об'єднання комп'ютерів, коли буде задіяна мінімально необхідна кількість зв'язків, щоб у цій мережі між кожною парою комп'ютерів був зв'язок (у тому числі і через проміжні комп'ютери).
У першому рядку записані два натуральних числа: – кількість комп'ютерів та – кількість з'єднань, які можна прокласти між певними парами цих комп'ютерів.
Далі слідують рядків, у кожному з яких наведено інформацію про кожне можливе з'єднання між комп'ютерами X_i та Y_i та вартість C_i прокладання такого з'єднання у формі трьох цілих чисел: X_i, Y_i та C_i (1 \le X_i, Y_i \le N, 1 \le i \le M).
У першому рядку виведіть одне число – кількість утворених мереж.
У другому рядку виведіть в порядку зростання максимальні вартості утворення кожної з мереж.
У третьому рядку виведіть в порядку зростання мінімальні вартості утворення кожної з мереж.
Приклад 1
