Сенсорна мережа
У відповідь на запит команди, що встановлювала задачі для SWERC 2010, в штаб-квартирі щойно було встановлено мережу датчиків. Організаційний комітет вселив у постановників задач непропорційний страх перед витоком секретної інформації про задачі.
Проте, в поспіху вони забули подумати про електромережу, необхідну для роботи датчиків. Через це система безпеки наразі не працює, але ми повинні виправдати велику кількість ресурсів, вкладених у неї, тому установка повинна бути готова до кінця змагання. Отже, вас просять розробити програму, яка допоможе електрику у його завданні.
Оскільки організаційний комітет не шкодував коштів, вони замовили датчики у престижної компанії. Кожен датчик виготовлений вручну, і на кожному з них написано число, яке означає рекомендовану напругу, яку слід застосувати для його правильного функціонування. Їх можна використовувати при вищих напругах, з підвищеним ризиком відмови, але ніколи при напрузі нижче рекомендованої. Електрик був вражений, коли йому дали датчики: майже всі вони мали різні рекомендовані напруги! Датчики були встановлені в будівлі таким чином, що кожен з них контролює рівно двоє дверей, і кожні двері контролюються принаймні одним датчиком. Тепер настав час для електрика забезпечити живлення датчиків. Він стикається з такими обмеженнями:
На щастя, немає потреби активувати всі датчики. Однак ми вимагатимемо, щоб підмножина датчиків, обрана для ввімкнення, забезпечувала контроль кожних дверей принаймні одним датчиком з підмножини.
Електрика повинна бути подана на один з активних датчиків, а потім розподілена до інших за допомогою проводів. Щоб не витрачати дроти, їх можна встановлювати, з'єднуючи пару сусідніх активних датчиків (під "сусідніми" ми маємо на увазі, що деякі двері контролюються обома з них). Оскільки ми повинні забезпечити енергією кожен активний датчик, не кожна підмножина датчиків підходить як обрана підмножина робочих датчиків.
Через вищезазначене, всі датчики будуть забезпечені однаковою напругою, яка не може бути нижчою за відповідні рекомендовані напруги.
Для простоти ми будемо називати підмножину датчиків, що задовольняє перші два обмеження, допустимою підмножиною. Мережа спроектована так, що набір усіх датчиків завжди є допустимим, але ми хотіли б взяти, можливо, меншу підмножину, щоб мінімізувати запас, визначений як максимум різниць, за абсолютною величиною, між числами, написаними на кожній парі датчиків у підмножині. (Це для того, щоб звести до мінімуму шанси на відмову).
Електрик не зміг вирішити завдання з пошуку допустимої підмножини набору датчиків, для якої запас є мінімальним. Тому електрична установка досі відсутня. Сьогодні ми просимо вас написати програму, щоб дізнатися відповідь, маючи мережу датчиків і рекомендовану напругу для кожного з датчиків.
Вхідні дані
Вхід складається з декількох тестових випадків, розділених одним порожнім рядком. Кожен тестовий випадок починається з рядка, що містить ціле число n (2 ≤ n ≤ 350), кількість дверей у будівлі. Наступний рядок містить інше ціле число, m (n-1 ≤ m ≤ n(n-1)/2), кількість датчиків у мережі. Тестовий випадок закінчується m рядками, що містять опис кожного з m датчиків. i-й з цих рядків містить три цілі числа, a (0 ≤ a ≤ n-1), b (0 ≤ b ≤ n-1) і w (1 ≤ w ≤ 2^15), у такому порядку. Цілі числа a і b представляють пару дверей, контрольованих i-м датчиком, а w — його рекомендовану напругу. Ви можете бути впевнені, що немає двох датчиків, які контролюють одні й ті ж двоє дверей.
Вхід закінчується рядком, що містить '0'.
Вихідні дані
Для кожного випадку ваша програма повинна вивести рядок, що містить мінімальний запас допустимої підмножини датчиків.