Let's Go Green
Хайрі — молодий, розумний і надзвичайно талановитий політик. Проте він вважає, що для досягнення успіху, особливо в політиці, важливо мати мережу особистих контактів. Наступного місяця відбудуться вибори до Верховної Ради його політичної партії, і Хайрі планує взяти в них участь, сподіваючись на перемогу. Для цього йому потрібна підтримка впливового політика.
Час обмежений, тому Хайрі розробляє стратегію. Якщо він не може зустрітися з головною особою безпосередньо, він планує скористатися допомогою інших політиків, щоб познайомитися з цим лідером. Для цього він моделює силу відносин між політиками.
Сила відносин між двома людьми визначається наступним чином: Вірний (1), Близький (2), Друзі (3) і Знайомий (4). Зазвичай один з політиків ініціює спілкування. Вороги не враховуються. Було б значно краще, якби вірний друг познайомив Хайрі з кимось, ніж просто знайомий. Тому Хайрі прагне мінімізувати суму сили відносин, які він використовує, щоб зустрітися з впливовим політиком.
Зі списку з N політиків, враховуючи їхні сили відносин, знайдіть шлях, через який Хайрі може зустрітися з впливовим політиком, при цьому мінімізуючи суму сил усіх використаних відносин.
Вхідні дані
Перша строка введення містить число T, яке вказує на кількість тестових випадків, 1 < T < 1000. Далі йдуть тестові випадки. Кожен випадок складається з кількох рядків. Перша строка містить 2 числа: N, що представляє кількість відносин, N ≤ 200, і M, що представляє кількість політиків, 5 ≤ M ≤ 20. Кожен з наступних N рядків містить три цілі числа, що представляють політика x, його/її друга y (0 ≤ x, y < M) і силу відносин z (1 ≤ z ≤ 4). Політик x=0 представляє Хайрі, а політик x=M-1 представляє головного політика.
Вихідні дані
Для кожного тестового випадку виведіть рядок у форматі Case #x:, де x — це номер випадку (починаючи з 1), після чого йде двокрапка, а потім послідовність політиків, яких потрібно зустріти. Якщо є кілька дійсних послідовностей політиків, виведіть будь-яку з них. Список має починатися з 0 (ідентифікатор Хайрі) і закінчуватися M-1, головним політиком. Якщо немає способу, щоб Хайрі міг зустрітися з головним політиком, виведіть -1.
Пояснення для першого випадку: Хайрі може попросити політика 1 (сила 2, близький) познайомити його з політиком 3 (сила 4, знайомий), який нарешті може познайомити Хайрі з політиком 4 (сила 4, знайомий). Таким чином, загальна сила, використана в цій ситуації, становить 2+4+4 = 10.
Хайрі може прямо поговорити з політиком 4 (сила 3, друг). Але замість цього, якщо Хайрі попросить політика 2 (сила 1, вірний) познайомити його з політиком 4 (сила 1, знову вірний) — загальна сила, використана в цій ситуації, становить 2, що краще, ніж інші дві ситуації, і Хайрі, ймовірно, справить краще враження.