쥐굴 터널

아르투로는 멸종 위기종인 친칠라를 가까이서 관찰하려고 칠레 안데스 산맥에 큰 저택을 샀다. 친칠라는 저택 아래 깊이 파 놓은 굴에서 살고, 굴 안을 한 바퀴 도는 경로를 따라 서로 쫓아다닌다. 새 굴은 30일에 한 번만 판다.

아르투로는 친칠라가 지나갈 때 자동으로 녹화를 시작하는 동작 감지 카메라를 굴에 달아 달라고 부탁했다. 가능한 순환 경로마다 카메라가 적어도 하나는 있어야 하고, 설치 비용의 합은 최소여야 한다.

굴은 교차점과, 교차점을 잇는 양방향 통로로 이루어진다. 순환 경로는 교차점 A에서 출발해 통로를 두 개 이상 지나 다시 A로 돌아오는 경로이고, 한 경로 안에서 같은 통로를 두 번 지나지는 않는다. 출발점은 어느 교차점이든 된다.

카메라는 교차점이 아니라 통로에 설치하며, 카메라 한 대의 비용은 그 통로의 길이와 같다. 가능한 모든 순환 경로에 카메라가 하나 이상 놓이도록 통로를 고르되, 비용의 합을 최소로 하라. 최소 비용과, 카메라가 설치된 통로 가운데 가장 긴 통로의 길이를 구하는 프로그램을 작성하라.

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

각 테스트 케이스의 첫 줄에는 교차점의 수 $S$와 통로의 수 $L$이 공백으로 구분되어 주어진다. ($0 < S < 10001$, $0 < L < 100001$) 교차점에는 $1$부터 $S$까지 번호가 붙어 있다. 이어지는 $L$개의 줄에는 통로가 하나씩 주어진다. 각 줄에는 통로가 잇는 서로 다른 두 교차점의 번호와 그 통로의 길이가 주어지며, 길이는 $1$ 이상 $5000$ 이하이다. 같은 두 교차점을 잇는 통로가 여러 개일 수 있다. 굴 전체는 하나로 연결되어 있다.

각 테스트 케이스마다 한 줄에 Case #X: D M 형식으로 출력한다. $X$는 $1$부터 시작하는 테스트 케이스 번호, $D$는 카메라 설치 비용의 최솟값, $M$은 카메라가 설치된 통로 가운데 가장 긴 통로의 길이다. 카메라가 하나도 필요 없으면 $D$와 $M$을 모두 $0$으로 출력한다.