Локальні мережі

У великій ІТ-компанії є $N$ комп’ютерів $N$ ($1$ ≤ $N$ ≤ $1000$). Ці комп’ютери потрібно об’єднати у локальну мережу або, якщо це неможливо – у декілька локальних мереж. Під локальною мережею мається на увазі система пов’язаних між собою комп’ютерів, у тому числі через проміжні комп’ютери. Керівництво компанії хоче прорахувати, мінімальну та максимально можливі вартості об’єднання комп’ютерів у мережу.

Завдання 1. Визначте максимальну вартість об’єднання комп’ютерів у локальну мережу, коли будуть задіяні усі можливі зв’язки між комп’ютерами. Якщо усі комп’ютери не можна поєднати в одну мережу (щоб між будь-якою парою комп’ютерів був зв’язок, у тому числі через проміжні комп’ютери), то побудуйте дві чи декілька локальних мереж, які не пов’язані між собою, але так, щоб були задіяні усі можливі зв’язки між комп’ютерами, які вказані у вхідних даних.

Завдання 2. Для побудованої в завданні 1 локальної мережі (або локальних мереж) визначте мінімальну вартість об’єднання комп’ютерів, коли буде задіяна мінімально необхідна кількість зв’язків, щоб у цій мережі між кожною парою комп’ютерів був зв’язок (у тому числі і через проміжні комп’ютери).

Giriş verilənləri

У першому рядку записані два натуральних числа: $N$ – кількість комп’ютерів та $M$ – кількість з’єднань, які можна прокласти між певними парами цих комп’ютерів.

Далі слідують $M$ рядків, у кожному з яких наведено інформацію про кожне можливе з’єднання між комп’ютерами $X_i$ та $Y_i$ та вартість $C_i$ прокладання такого з’єднання у формі трьох цілих чисел: $X_i$, $Y_i$ та $C_i$ ($1$ ≤ $X_i$, $Y_i$ ≤ $N$, $1$ ≤ $i$ ≤ $M$).

Çıxış verilənləri

У першому рядку виведіть одне число – кількість утворених мереж.

У другому рядку виведіть в порядку зростання максимальні вартості утворення кожної з мереж.

У третьому рядку виведіть в порядку зростання мінімальні вартості утворення кожної з мереж.

Nümunələr

Qeyd