누구를 아느냐가 문제다

한신이는 젊고 똑똑한 정치인이다. 그래도 자기 성공을 받쳐 주는 것은 인간관계라고 믿는다. 다음 달 국회의원 선거에서 한신이는 자기 당이 이기기를 바라고, 그러려면 최고의원의 지지가 필요하다.

최고의원을 직접 만날 수 없으면 그를 아는 사람을 거쳐 소개받으면 된다. 그래서 한신이는 정치인 사이의 친밀도를 네 단계로 정리했다.

최측근 [1] / 측근 [2] / 비즈니스 관계 [3] / 지인 [4]

기록된 관계는 반드시 이 네 단계 중 하나이고, 적(enemy)은 없다.

한신이는 지인보다 최측근에게 소개받고 싶어 한다. 그래서 최고의원까지 이어지는 소개 사슬의 친밀도 합을 될 수 있는 대로 작게 만들려고 한다.

정치인 $M$명과 이들 사이의 친밀도가 주어진다. 0번 정치인(한신이)에서 $M-1$번 정치인(최고의원)까지 이어지는 소개 사슬의 친밀도 합 중 가장 작은 값을 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 < T < 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 관계의 수 $N$ ($N \le 20$)과 정치인의 수 $M$ ($5 \le M \le 20$)이 주어진다. 이어지는 $N$개 줄에는 정치인 $x$, 그의 친구 $y$ ($0 \le x, y < M$), 두 사람의 친밀도 $z$ ($1 \le z \le 4$)가 주어진다. 관계는 양쪽 모두에 성립하므로 소개는 $x$에서 $y$로도 가고 $y$에서 $x$로도 간다. 0번 정치인은 한신이고, $M-1$번 정치인은 최고의원이다.

각 테스트 케이스마다 한 줄에 Case #x: v 형식으로 출력한다. $x$는 1부터 시작하는 케이스 번호이고, $v$는 0번 정치인에서 $M-1$번 정치인까지 이어지는 소개 사슬의 친밀도 합 중 가장 작은 값이다. 한신이가 최고의원에게 닿을 수 없으면 $v$ 자리에 -1을 출력한다.

첫 번째 예제의 첫 테스트 케이스를 보자. 한신이가 1번(자신의 측근 [2])에게 3번(1번의 지인 [4])을 소개받고 3번이 4번(3번의 지인 [4])을 소개하면 친밀도 합은 $2+4+4=10$이다. 4번(자신의 비즈니스 관계 [3])에게 바로 말을 걸면 3이다. 2번(자신의 최측근 [1])에게 4번(2번의 최측근 [1])을 소개받으면 합이 $1+1=2$로 가장 작으니 답은 2다.