[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”,否则输出一个整数,为抢修的最优方案所需要的总时间。


样例输入

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

提示

陕西省队选拔赛


题目来源

鸣谢 HYF上传