흥미로운 나들이

먼 곳에서 온 손님들을 맞이하여 시내에서 가장 흥미로운 장소를 함께 둘러보려고 합니다.

둘러보고 싶은 흥미로운 관광지가 $N$곳 있습니다. 교통수단은 $N-1$개가 있으며, 각 교통수단은 두 관광지를 양방향으로 연결합니다. 어떤 관광지에서 다른 관광지로 가는 경로는 교통수단을 두 번 이상 쓰지 않고 가는 방법이 정확히 하나뿐입니다.

각 교통수단을 한 번 쓰는 데 드는 비용은 알고 있습니다(쓸 때마다 비용을 냅니다). 출발 관광지와 도착 관광지는 자유롭게 정할 수 있으며, 같을 수도 다를 수도 있습니다. 출발지까지 가는 비용과 도착지에서 돌아오는 비용은 고려하지 않고, 투어 중 관광지 사이를 이동하는 비용만 계산합니다. 모든 관광지를 적어도 한 번씩 둘러보는 가장 저렴한 방법의 비용은 얼마입니까?

첫 줄에 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 나옵니다. 각 테스트 케이스의 첫 줄에는 관광지의 수 $N$이 주어집니다. 그다음 $N-1$개의 줄이 이어지며, i번째 줄에는 정수 $A_i$, $B_i$, $C_i$가 주어집니다. 이는 i번째 교통수단이 관광지 $A_i$와 $B_i$를 양방향으로 잇고, 한 번 사용할 때마다 $C_i$코인이 든다는 뜻입니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력합니다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 관광지를 적어도 한 번씩 방문하는 투어의 최소 비용입니다.

$1≤T≤100$.

모든 $i$에 대해 $1≤A_i<B_i≤N$.

주어진 교통수단만으로 어떤 두 관광지 사이든 이동할 수 있습니다. (이 조건과 앞선 조건에 따라 관광지와 교통수단은 뿌리가 없는 트리를 이룹니다.)

모든 $i$에 대해 $1≤C_i≤10^9$.

예제 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}$보다 클 수 있다는 점에 유의하세요.