탐험 레이스

새내기 환영 탐험 레이스가 열린다. 각 팀은 정해진 순서 없이 모든 체크포인트를 방문해야 하며, 각 체크포인트에서는 정해진 활동을 수행한다. 팀은 체크포인트를 방문하는 순서를 자유롭게 정할 수 있다.

주최 측은 신입생이 길을 잃지 않도록 일부 경로에만 진행 요원을 배치하고, 학생들은 요원이 배치된 경로만 이용할 수 있게 하려 한다. 요원의 수가 제한되어 있으므로 배치하는 경로의 전체 길이 합을 가능한 한 줄이면서, 모든 두 체크포인트 사이를 이동할 수 있는 방법이 존재하도록 해야 한다. 각 경로는 두 체크포인트 $a$와 $b$를 양방향으로 연결하며 길이는 $d$이고, 모든 경로의 길이는 $500$ 이하이다. 각 테스트 케이스에 대해 배치해야 하는 경로 길이 합의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다($1 \le T \le 10$). 각 테스트 케이스의 첫째 줄에는 체크포인트의 개수 $N$과 고려할 경로의 개수 $M$이 주어진다($1 \le N \le 20$, $1 \le M \le N(N-1)$). 이어지는 $M$개의 줄에는 세 정수 $a$, $b$, $d$가 주어진다($1 \le a, b \le N$, $1 \le d \le 500$). 이는 체크포인트 $a$와 체크포인트 $b$를 연결하는 길이 $d$인 경로가 있음을 의미한다.

각 테스트 케이스마다 Case #x: y meters 형식으로 한 줄에 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 배치해야 하는 경로 길이 합의 최솟값이다.