Давайте станем экологичными
Хайри — молодой, умный и очень талантливый политик. Однако он убеждён, что для достижения успеха, особенно в политике, необходима сеть личных контактов. В следующем месяце состоятся выборы в Высший совет его политической партии, и Хайри намерен участвовать, надеясь на победу. Для этого ему нужна поддержка влиятельного политика.
Времени мало, поэтому Хайри разрабатывает стратегию. Если он не сможет встретиться с лидером напрямую, он планирует использовать других политиков, чтобы быть представленным этому лидеру. Для этого он моделирует силу отношений между политиками.
Сила отношений между двумя людьми определяется следующим образом: Верный (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, что лучше, чем в других двух ситуациях, и Хайри с большей вероятностью произведет хорошее впечатление.