Давайте станемо екологічними#6370

Давайте станемо екологічними

10 секунд

64 мегабайти

Легка

Хайрі — молодий, розумний і надзвичайно талановитий політик. Проте він вважає, що для досягнення успіху, особливо в політиці, важливо мати мережу особистих контактів. Наступного місяця відбудуться вибори до Вищої ради його політичної партії, і Хайрі планує взяти в них участь, сподіваючись на перемогу. Для цього йому потрібна підтримка впливового політика.

Час обмежений, тому Хайрі розробляє стратегію. Якщо він не може зустрітися з головною особою безпосередньо, він планує скористатися допомогою інших політиків, щоб познайомитися з цим лідером. Для цього він моделює силу відносин між політиками.

Сила відносин між двома людьми визначається наступним чином: Вірний ( $1$ ), Близький ( $2$ ), Друзі ( $3$ ) і Знайомий ( $4$ ). Зазвичай один із політиків ініціює спілкування. Вороги не враховуються. Було б значно краще, якби вірний друг познайомив Хайрі з кимось, ніж просто знайомий. Тому Хайрі прагне мінімізувати суму сил відносин, які він використовує, щоб зустрітися з впливовим політиком.

Зі списку з $N$ політиків, враховуючи їхні сили відносин, знайдіть шлях, через який Хайрі може зустрітися з впливовим політиком, при цьому мінімізуючи суму сил усіх використаних відносин.

Ваше завдання — запропонувати послідовність політиків, яких Хайрі повинен зустріти, щоб його представили впливовому політику.

Вхідні дані

Перша строка введення містить число $T$ , яке вказує на кількість тестових випадків, $1 < T < 1000$ 1 < T < 1000. Далі йдуть тестові випадки. Кожен випадок складається з кількох рядків. Перша строка містить $2$ числа: $N$ , що представляє кількість відносин, $N \leq 200$ N \leq 200, і $M$ , що представляє кількість політиків, $5 \leq M \leq 20$ 5 \leq M \leq 20. Кожен із наступних $N$ рядків містить три цілі числа, що представляють політика $x$ , його/її друга $y$ ( $0 \leq x, y < M$ 0 \leq x, y < M) і силу відносин $z$ ( $1 \leq z \leq 4$ 1 \leq z \leq 4). Політик $x = 0$ x = 0 представляє Хайрі, а політик $x = M - 1$ x = M - 1 представляє головного політика.

Вихідні дані

Для кожного тестового випадку виведіть рядок у форматі Case #x:, де $x$ — це номер випадку (починаючи з $1$ ), після чого йде двокрапка, а потім послідовність політиків, яких потрібно зустріти. Якщо є кілька дійсних послідовностей політиків, виведіть будь-яку з них. Список має починатися з $0$ (ідентифікатор Хайрі) і закінчуватися $M - 1$ M - 1, головним політиком. Якщо немає способу, щоб Хайрі міг зустрітися з головним політиком, виведіть $- 1$ .

Приклади

Приклад 1

Примітка

Пояснення для першого випадку: Хайрі може попросити політика $1$ (сила $2$ , близький) познайомити його з політиком $3$ (сила $4$ , знайомий), який нарешті може познайомити Хайрі з політиком $4$ (сила $4$ , знайомий). Таким чином, загальна сила, використана в цій ситуації, становить $2 + 4 + 4 = 10$ 2 + 4 + 4 = 10.

Хайрі може прямо поговорити з політиком $4$ (сила $3$ , друг). Але замість цього, якщо Хайрі попросить політика $2$ (сила $1$ , вірний) познайомити його з політиком $4$ (сила $1$ , знову вірний) — загальна сила, використана в цій ситуації, становить $2$ , що краще, ніж інші дві ситуації, і Хайрі, ймовірно, справить краще враження.