[Snoi2013]Quare

时间限制：2s 空间限制：128MB

题目描述

4.20四川芦山地震发生后，抗震救灾委员会接到一个紧急任务，四川省给
该委员会发了一份地图，这份地图给出了该省一些城市的情况：任两个城市是
用一条或多条公路连接起来的，也可以没有公路连接，但是每个城市都可以直
接或间接地到达另外的城市，注意这些公路是可以双向行驶的。由于最近余震、
暴雨造成泥石流倾泻，使得车辆在这些公路上行驶很不安全，于是四川省决定
尽快对部分公路进行抢修，以保障救援车辆行车安全。
该省对所有的公路情况都进行了勘察，分析估计了抢修某段公路所需要花
费的时间，并记录在地图中。现在该省希望抗震救灾委员会能找到一个方案，
该方案决定出哪些公路需要抢修，使得抢修后的公路仍能保证任意两个城市之
间都能直接或间接地相连，同时为了安全起见，即使某一条抢修的公路被泥石
流阻断了，任意两城市仍能保持这个性质。由于时间紧迫，抗震救灾委员会还
需保证找到的这个方案总抢修时间最短。

输入格式

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

输出格式

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

样例输入

样例输出

6
impossible

提示

陕西省队选拔赛

题目来源

鸣谢 HYF上传