P5776 [SNOI2013] Quare

After the 4.20 Lushan earthquake in Sichuan, the Earthquake Relief Committee received an urgent task. Sichuan Province sent the committee a map describing some cities in the province: between any two cities, there may be one or more roads connecting them, or there may be no road at all, but every city can reach every other city directly or indirectly. Note that these roads are two-way. Due to recent aftershocks and heavy rain causing mudslides, it has become unsafe for vehicles to drive on these roads, so Sichuan Province decided to repair some of the roads as soon as possible to ensure the safety of rescue vehicles. The province surveyed all roads, estimated the time needed to repair each road segment, and recorded it on the map. Now the province hopes the committee can find a plan that decides which roads to repair, such that after repair, any two cities are still connected directly or indirectly. At the same time, for safety, even if any one repaired road is blocked by a mudslide, any two cities must still remain connected in this sense. Due to time pressure, the committee must also ensure that the total repair time of the plan is minimized.

The first line contains an integer $T$, the number of test cases. Then the description of each test case follows in order. First come two integers $n, m$, representing the number of cities and the number of roads. The next $m$ lines each contain three integers $x, y, c$ describing one road: a road between city $x$ and city $y$, and repairing this road requires $c$ units of time. Note that there may be multiple roads between the same two cities as mentioned above.

Output the result for each test case in order. If no suitable plan can be found, output one line `impossible`. Otherwise, output one integer, the total time required by the optimal repair plan.

For $100\%$ of the testdata, $1 \leq T \leq 3$, $1 \leq n \leq 12$, $1 \leq m \leq 40$, $1 \leq c \leq 5\times 10^4$. Translated by ChatGPT 5