Відрізняється від попередньої версії «Алгоритм Краскала — 1» лише тим, що результати потрібно вивести більш детально. Якщо граф незв'язний, то, як і в попередній задачі, відповідь повинна бути просто рядком з єдиним словосполученням NON-CONNECTED. А для зв'язного графа відповідь повинна описувати саме дерево.

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

Вхідні дані

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

Результати

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

• якщо граф незв'язний – єдине словосполучення NON-CONNECTED (великими латинськими буквами, без лапок),
• якщо зв'язний – перший рядок має містити єдине ціле число: сумарну довжину ребер побудованого остовного (кістякового) дерева; далі мають бути N рядків, кожен з яких має містити список суміжності відповідної вершини. Формат списку суміжності: пишеться, яка вершина, пробіл, двокрапка, далі усі вершини, куди йдуть ребра з цієї, у вигляді: пробіл, номер вершини, куди йде ребро, відкривна дужка (, довжина ребра, закривна дужка ). Рядки мають бути виведені згідно порядку номерів вершин (тих, що зліва від :). Переліки всередині кожного рядка теж повинні бути впорядковані за номерами вершин. Між кожними сусідніми різними ребрами одного переліку повинні бути кома і пробіл. Закінчувати рядок комою чи комою з пробілом (ставити їх після опису останнього в рядку ребра) заборонено.

Приклади

Вхід

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

Результат

19
0 : 4(10)
1 : 3(2)
2 : 3(4), 4(3)
3 : 1(2), 2(4)
4 : 0(10), 2(3)

Вхід

100 1
17 42 111

Результат

NON-CONNECTED

Примітки

Див. примітки до попередньої задачі «Алгоритм Краскала» та до задачі «Алгоритм Дейкстри за M log N».