로드 트립

한 여행 밴드가 자기 주(state)의 모든 주요 도시에서 공연을 하고 출발했던 도시로 다시 돌아오려고 한다. 각 도시에서 공연장을 빌리는 비용을 따져 보니 예산이 빠듯해서, 정확히 한 도시는 건너뛰어야(그곳에서는 공연하지 않아야) 한다.

밴드는 사용할 도로를 이미 골라 두었는데, 고른 도로에는 사이클이 전혀 없으면서도 모든 도시를 연결한다. 즉, 고른 도로들은 하나의 트리를 이룬다. 각 도로는 양방향이며 몇 번이든 오갈 수 있다.

밴드는 항상 1번 도시에서 출발해 1번 도시로 돌아오므로 1번 도시는 절대 건너뛸 수 없다. 어떤 도시를 건너뛰면 그 도시와 그 도시에 닿는 도로들이 사라지며, 남은 도시들은 여전히 고른 도로만으로 모두 방문할 수 있어야 한다. 건너뛸 수 있는 도시들 중에서 왕복 이동 거리가 가장 짧아지는 도시 하나를 골라 건너뛴다.

이때 가능한 가장 짧은 왕복 이동 거리를 출력하라.

첫째 줄에 데이터 세트의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 세트가 아래 형식으로 주어진다.

각 데이터 세트의 첫째 줄에는 도시의 수 $V$와 도로의 수 $E$가 주어진다 ($2 \le V \le 100$, $1 \le E \le 100$).

이어지는 $E$개의 줄에는 각각 양방향 도로 하나가 세 정수 $a_i$, $b_i$, $d_i$로 주어진다. 이는 도시 $a_i$와 도시 $b_i$ 사이에 길이가 $d_i$인 도로가 있다는 뜻이다 ($1 \le a_i, b_i \le V$). 도로에는 사이클이 없으므로, 도로들은 모든 $V$개의 도시를 연결하는 하나의 트리를 이룬다. 밴드는 항상 1번 도시에서 출발한다.

각 데이터 세트마다 Data Set x: 형식의 줄을 출력한다. 여기서 $x$는 데이터 세트의 번호이다(1부터 시작). 다음 줄에는 밴드가 가장 알맞은 도시 하나를 건너뛰고 나머지 모든 도시를 방문한 뒤 1번 도시로 돌아올 때의 최소 이동 거리를 출력한다. 각 데이터 세트를 출력한 뒤에는 빈 줄을 하나 출력한다.