题目描述

4.20 四川芦山地震发生后，抗震救灾委员会接到一个紧急任务，四川省给该委员会发了一份地图，这份地图给出了该省一些城市的情况：任两个城市是用一条或多条公路连接起来的，也可以没有公路连接，但是每个城市都可以直接或间接地到达另外的城市，注意这些公路是可以双向行驶的。由于最近余震、暴雨造成泥石流倾泻，使得车辆在这些公路上行驶很不安全，于是四川省决定尽快对部分公路进行抢修，以保障救援车辆行车安全。

该省对所有的公路情况都进行了勘察，分析估计了抢修某段公路所需要花费的时间，并记录在地图中。现在该省希望抗震救灾委员会能找到一个方案，该方案决定出哪些公路需要抢修，使得抢修后的公路仍能保证任意两个城市之间都能直接或间接地相连，同时为了安全起见，即使某一条抢修的公路被泥石流阻断了，任意两城市仍能保持这个性质。

由于时间紧迫，抗震救灾委员会还需保证找到的这个方案总抢修时间最短。

输入格式

输入文件有多组数据，第一行为一个整数 $t$，为 $case$ 总数，
接下来按顺序给出每个 $case$ 描述，
首先是两个整数 $n$，$m$ 分别表示城市数量和公路数量，
下面 $m$ 行每行 $3$ 个整数 $x,y,c$ 描述了一条公路的情况：$x$ 城市与 $y$ 城市之间的一条公路，抢修该公路需要 $c$ 个单位时间。

注意上面所说的两城市间可能有多条公路。

输出格式

按顺序输出每个 $case$ 的结果，如果找不到一条合适的方案，则输出一行 impossible，否则输出一个整数，为抢修的最优方案所需要的总时间。

2
4 6
1 2 1
1 3 2
1 3 3
2 4 2
3 4 1
2 3 1
2 1
1 2 3

6
impossible

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 12$，$1\le m\le 40$。

题目来源

陕西省队选拔赛

鸣谢HYF上传