Напишіть програму, яка знаходитиме остовне (кістякове, spanning) дерево мінімальної ваги неорієнтованого зваженого графу з додатними довжинами ребер. Програма повинна працювати швидко для великих розріджених графів (максимальна кількість вершин – десятки тисяч, ребер – сотні тисяч).

Вхідні дані

Перший рядок містить два числа N та M, розділені пробілом – кількість вершин та кількість ребер графа. Далі йдуть M рядків, кожен з яких містить по три цілі числа, розділені пробілами. Перші два з них різні, у межах від 0 до N–1 кожне, і позначають кінці відповідного ребра, третє – у межах від 1 до ~10^9~ і позначає довжину цього ребра. Гарантовано, що всі ребра мають різні довжини.

Результати

Виведіть єдиний рядок, який має містити:

• якщо граф незв'язний – єдине словосполучення NON-CONNECTED (великими латинськими буквами, без лапок),
• якщо зв'язний – сумарну довжину ребер побудованого остовного (кістякового) дерева.

Приклади

Вхід

5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10

Результат

19

Вхід

100 1
17 42 111

Результат

NON-CONNECTED

Примітки

Зверніть увагу, що при вказаних обмеженнях на довжини та кількість ребер можлива ситуація, коли сума довжин ребер дерева не поміщається у тип int. Скористайтеся цілим 64-бітовим типом.

Алгоритму Краскала абсолютно не потрібно, щоб граф був поданий списками суміжності. Тому, на відміну від попередніх графових задач, формувати при читанні графа списки суміжності недоцільно. Натомість, потрібно сортувати ребра за довжиною, як у задачі «Сортування ребер за довжиною». І взагалі, ~\approx~95% розв'язку цієї задачі полягає в тому, щоб правильно поєднати задачі «Сортування ребер за довжиною» та «Неперетинні множини (disjoint sets)».