시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 35 16 13 44.828%

문제

한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한것이라고 믿고있다. 다음달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다.

이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날수 없다면 그를 알고있는 인맥을 이용하여 만날것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다.

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

[두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(enemy)는 존재하지 않는다.]

한신이는 지인보다는 최측근 친구에게 소개받기 원한다. 그래서 최고의원을 만나기까지의 인맥간 친밀도의 합을 최소화하고 싶어한다.

N명의 정치인 명단으로부터 그들의 인맥 친밀도가 주어진다. 정치인 리스트를 보고 한신이가 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하면 된다.

입력

맨위 첫번째 줄에 T(1 <T< 100)는 테스트케이스 수를 의미한다. 이것을 따라 다음줄에 각 테스트 케이스가 주어지는데, 첫번째 줄에는 N과 M이 주어진다. N(N ≤ 20)은 관계의 갯수를 의미하며, M(5 ≤M≤ 20)은 정치인의 수를 나타낸다. 이 다음 N줄에는 정치인 x, 그의 친구 y (0 ≤x,y< M), 두사람간의 친밀도 z(1 ≤z≤ 4)를 입력받는다. 정치인 0번은 한신이를 나타내고 M-1은 최고의원을 의미한다.

출력

각 테스트 케이스는 "Case #x: "의 형식으로 출력되며 x는 케이스 번호(1부터 시작)을 의미한다. 콜론뒤에 한신이가 최고의원을 만날수 있다면 0번 정치인(한신이)를 시작으로 M-1번 정치인(최고의원)까지 만난 순서대로 출력하면 되고, 최고의원을 만날수 없는 경우엔 -1을 출력하면 된다.

예제 입력

2
7 5
0 1 2
1 3 4
0 2 1
0 4 3
3 2 3
3 4 4
2 4 1
3 5
0 1 2
1 3 4
4 2 1

예제 출력

Case #1: 0 2 4
Case #2: -1

힌트

첫번째 테스트 케이스에서 보면 한신이는 1번 정치인(한신이의 측근[2])에게 3번 정치인(1번 정치인의 지인[4])을 소개받고, 이 3번 정치인은 4번 정치인(3번 정치인의 지인[4])을 만나는 경우 2+4+4 = 10이다.

한신이가 곧바로 4번 정치인(한신이의 비즈니스관계[3])에게 얘기할수 있지만 대신에 2번 정치인(한신이의 최측근[1])에게 4번 정치인(2번 정치인의 최측근[1])을 소개 받아 만난다면 한신이는 더 좋은 인상으로 최고의원을 만날수 있을것이다.