Ви відповідаєте за проектування мережі в кампусі між будинками та дуже турбуєтеся про її надійність та вартість. Ви вирішили додати деяку надлишковість мережі, зберігаючи при цьому її якомога дешевшою. Зокрема, Ви хочете побудувати таку саму дешеву мережу, що якщо деяка одна лінія зв'язку перестане працювати, проте зв'язок між усіма будинками все ще буде існувати. Таку мережу будемо називати мінімальною надійною мережею.

Вхідні дані

Складається з декількох тестів. Кожний тест починається з рядка, що містить пару цілих чисел n (n ≤ 15) та m (m ≤ 20) - кількість будинків (пронумерованих від 1 до n) та кількість можливих сполучень між будинками. Кожний з наступних m рядків має вигляд b1 b2c (усі числа натуральні), який вказує на те, що вартість сполучення будинків b1 та b2 дорівнює с. Усі зв'язки двонаправлені.

Останній тест містить n = m = 0 та не обробляється.

Вихідні дані

Для кожного теста вивести один рядок, що містить вартість мінімальної надійної мережі. Якщо така мережа існує, то вивід повинен мати формат:

The minimal cost for test case p is c.

де p номер теста (починаючи з 1), а c вартість. Якщо надійної мережі не існує, то слід вивести наступний рядок:

There is no reliable net possible for test case p.