흥미로운 나들이

당신은 다른 지역에서 온 방문객들을 맞이하고 있으며, 그들을 데리고 나가 마을에서 가장 흥미로운 장소들을 보여 주고 싶다.

관광하려는 흥미로운 명소가 $\mathbf{N}$개 있다. 당신은 $\mathbf{N}-1$개의 흥미로운 교통수단을 파악했다. 각 교통수단은 한 쌍의 명소를 양방향으로 연결한다. 다행히도, 어떤 교통수단도 한 번보다 많이 이용하지 않고 임의의 흥미로운 명소에서 다른 명소로 가는 방법은 정확히 하나뿐이다.

각 교통수단을 단 한 번 이용할 때 일행에게 드는 비용을 알고 있다(이용할 때마다 한 번씩 지불한다). 관광의 시작 명소와 끝 명소는 직접 정할 수 있으며, 두 명소는 같을 수도 있고 다를 수도 있다. 시작 지점까지 가는 비용이나 끝 지점에서 돌아오는 비용은 고려할 필요가 없으며, 관광 도중 명소 사이를 이동하는 교통비만 고려하면 된다. 각 명소를 적어도 한 번씩 모두 둘러보는 가장 저렴한 방법은 무엇인가?

제한

시간 제한: 10초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{A_i} \lt \mathbf{B_i} \le \mathbf{N}$. 입력으로 주어진 교통수단만 이용하여 어떤 명소 쌍 사이든 이동할 수 있다. (이 제한과 이전 제한으로부터 명소와 교통수단이 루트 없는 트리를 이룬다는 것을 알 수 있다.) 모든 $i$에 대해 $1 \le \mathbf{C_i} \le 10^9$.

테스트 세트 1 (Visible Verdict)

$2 \le \mathbf{N} \le 10$.

테스트 세트 2 (Hidden Verdict)

$2 \le \mathbf{N} \le 1000$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 관광하려는 명소의 수를 나타내는 정수 하나 $\mathbf{N}$이 포함된 한 줄로 시작한다. 이어서 $\mathbf{N}-1$개의 줄이 주어진다. 이 줄들 중 $i$-번째 줄에는 세 정수 $\mathbf{A_i}$, $\mathbf{B_i}$, $\mathbf{C_i}$이 주어지며, 이는 $i$-번째 교통수단을 이용할 때마다 $\mathbf{C_i}$코인의 비용으로 일행을 명소 $\mathbf{A_i}$에서 명소 $\mathbf{B_i}$으로, 또는 명소 $\mathbf{B_i}$에서 명소 $\mathbf{A_i}$로 이동시킬 수 있음을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$은 각 명소를 적어도 한 번 방문하는 관광의 최소 비용을 나타내는 정수이다.

예제 케이스 #1에서(아래 그림 참조), 최적 경로는 다음 명소들을 지나간다: $2, 3, 1, 3, 4, 5, 4, 6$. 이 경로는 위 그림에서 빨간 선으로 표시되어 있다.

예제 케이스 #2에서(위 그림 참조), 예제 케이스 #1의 구성과 비교해 달라진 유일한 점은 명소 $1$와 $3$ 사이의 교통비가 $10$에서 $35$로 더 비싸졌다는 것이다. 이 상황에서 경로 $2, 3, 1, 3, 4, 5, 4, 6$의 비용은 $150$이며, 이 경로는 최적이 아니다. 대신 최적 경로는 $2, 3, 4, 6, 4, 5, 4, 3, 1$이며, 그림에도 빨간색으로 표시되어 있다.

예제 케이스 #3에서 답이 $2^{32}$보다 클 수도 있다는 점에 유의하라.