Khairy is a young, smart and highly talented politician. However, he still believes that for success, and especially to obtain something, one's network of personal contacts is essential. Next month will be the Supreme Council election of his political party. He wants to contest and really hope to win in the election. Therefore, support from top influential politician is needed. \includegraphics{https://static.e-olymp.com/content/11/113d5821aa4d6484d8c24b2c255096702908dc92.jpg} Time is running out, therefore he plans a strategy. If he cannot meet the top person directly he will use other politicians to introduce him to this top leader. In order to do this, he models the strength of relationship among the politicians. The strength of relationship between two people is represented as follows: Faithful (\textbf{1}), Close (\textbf{2}), Buddies (\textbf{3}) and Acquaintance (\textbf{4}). Between two politicians, either one of them will normally stimulate the communication. No representation for enemy. It will be much better if a faithful friend introduces Khairy to someone rather than an acquaintance. So Khairy wants to minimize the sum of strength of the relations he is using to meet the top influential politician. From a list of \textbf{N} politicians, given their relationship strengths, find a list of politicians so that Khairy meets the top influential politician through them while the sum of strength of all the relationships he used is minimized. Your task is to come out with a sequence of politicians that Khairy needs to meet in order to get introduced to the top influential politician. \InputFile The first line of input is \textbf{T} which is the number of cases, \textbf{1} < \textbf{T} < \textbf{1000}. This is followed by the test cases. Each case consists of several lines. The first line contains \textbf{2} numbers, first is \textbf{N} which represents the number of relationships, \textbf{N} ≤ \textbf{200}, and \textbf{M} which represents the number of politicians, \textbf{5} ≤ \textbf{M} ≤ \textbf{20}. Each of the next \textbf{N} lines contains three integers that represent politician \textbf{x}, his/her friend \textbf{y} (\textbf{0} ≤ \textbf{x}, \textbf{y} < \textbf{M}) and the strength of relationship \textbf{z} (\textbf{1} ≤ \textbf{z} ≤ \textbf{4}). Politician \textbf{x=0 }represents Khairy and politician \textbf{x=M-1} represents the top politician. \OutputFile For each test case, the output contains a line in the format \textbf{Case #x:} where \textbf{x} is the case number (starting from \textbf{1}) followed by a colon, followed by a sequence of politicians to meet. If there is multiple valid sequence of politicians print any of them. The list must start with \textbf{0} (Khairy's id) and end with \textbf{M-1}, the top politician. If there is no way Khairy can meet the to politician, print \textbf{-1}. \textit{\textbf{Explanation for the first case}}: Khairy can ask politician \textbf{1} (strength 2, close) to introduce him to politician \textbf{3 }(strength \textbf{4}, acquaintance), who can finally introduce Khairy to politician \textbf{4} (strength \textbf{4}, acquaintance). In that way total strength used in this situation is \textbf{2+4+4 = 10}. Khairy can straightly talk to politician \textbf{4} (strength \textbf{3}, buddy). But instead if Khairy asks politician \textbf{2} (strength \textbf{1}, faithful) to introduce him to politician \textbf{4} (strength \textbf{1}, again faithful) -- the total strength used in this situation is \textbf{2}, which is better than the other two situations and Khairy is more likely to make a good impression.