Road Trip

A traveling band wants to play a show in every major city in their state and then return to the city they started from. After looking at the cost of renting a venue in each city, they realize their tight budget lets them skip playing in exactly one city.

The band has already chosen which roads to use, and the chosen roads contain no cycles while still connecting every city — that is, the chosen roads form a tree. Each road is two-way and may be driven any number of times.

The band always starts and finishes at city 1, so they can never skip city 1. When they skip a city, that city and the roads touching it are removed, and every remaining city must still be reachable over the chosen roads. Among all cities they are allowed to skip, they pick the one that makes their round trip as short as possible.

Output the length of that shortest possible round trip.

The first line contains the number $K$ of data sets. The $K$ data sets follow, each in the form described below.

The first line of a data set contains two integers $V$ and $E$, the number of cities and the number of roads, where $2 \le V \le 100$ and $1 \le E \le 100$.

Each of the next $E$ lines describes one two-way road with three integers $a_i$, $b_i$, $d_i$, meaning there is a road of length $d_i$ between city $a_i$ and city $b_i$ ($1 \le a_i, b_i \le V$). The roads contain no cycles, so they form a tree that connects all $V$ cities. The band always starts at city 1.

For each data set, print a line of the form Data Set x:, where $x$ is the number of the data set (starting from 1). On the next line, print the minimum distance the band travels when it skips the best single city, visits every remaining city, and returns to city 1. Print one blank line after each data set.