Стрункий Рядок
Дано неорієнтований зважений граф G. Потрібно знайти одне з остовних дерев, визначених наступним чином.
Граф G є впорядкованою парою (V, E), де V — це множина вершин {v_1, v_2, ..., v_n}, а E — це множина неорієнтованих ребер {e_1, e_2, ..., e_m}. Кожне ребро e має свою вагу w(e).
Остовне дерево T — це дерево (зв'язний підграф без циклів), яке з'єднує всі n вершини за допомогою n−1 ребер. Стрункість остовного дерева T визначається як різниця між найбільшою вагою та найменшою вагою серед n−1 ребер T.
Рисунок 1: Граф G та ваги ребер
Наприклад, граф G на Рисунку 1(a) має чотири вершини {v_1, v_2, v_3, v_4} та п'ять неорієнтованих ребер {e_1, e_2, e_3, e_4, e_5}. Ваги ребер: w(e_1) = 3, w(e_2) = 5, w(e_3) = 6, w(e_4) = 6, w(e_5) = 7, як показано на Рисунку 1(b).
Рисунок 2: Приклади остовних дерев G
Існує кілька остовних дерев для G. Чотири з них зображені на Рисунку 2(a)'(d). Остовне дерево T_a на Рисунку 2(a) має три ребра, ваги яких 3, 6 і 7. Найбільша вага — 7, а найменша вага — 3, тому стрункість дерева T_a дорівнює 4. Стрункість остовних дерев T_b, T_c і T_d, показаних на Рисунку 2(b), (c) і (d), дорівнює 3, 2 і 1 відповідно. Легко побачити, що стрункість будь-якого іншого остовного дерева більша або дорівнює 1, отже, остовне дерево T_d на Рисунку 2(d) є одним з найстрункіших остовних дерев, стрункість якого дорівнює 1.
Ваше завдання — написати програму, яка обчислює найменшу стрункість.
Вхідні дані
Вхід складається з кількох наборів даних, за якими слідує рядок, що містить два нулі, розділені пробілом. Кожен набір даних має наступний формат.
n m
a_1 b_1 w_1
...
a_m b_m w_m
Кожен елемент введення в наборі даних є невід'ємним цілим числом. Елементи в рядку розділені пробілом.
n — це кількість вершин, а m — кількість ребер. Можна припустити, що 2 ≤ n ≤ 100 і 0 ≤ m ≤ n(n−1)/2. a_k і b_k (k = 1, ..., m) є додатними цілими числами, меншими або рівними n, які представляють дві вершини v_ak і v_bk, з'єднані k-м ребром e_k. w_k є додатним цілим числом, меншим або рівним 10000, що вказує на вагу e_k. Можна припустити, що граф G = (V, E) є простим, тобто не має петель (які з'єднують одну й ту ж вершину) і паралельних ребер (які є двома або більше ребрами, обидва кінці яких є одними й тими ж двома вершинами).
Вихідні дані
Для кожного набору даних, якщо граф має остовні дерева, слід вивести найменшу стрункість серед них. В іншому випадку, слід вивести −1. Вивід не повинен містити зайвих символів.