描述

金刚是特兰西瓦尼亚令人敬畏但公正的统治者。王国由两座城市和$N$个$（N < 150）$城镇组成，部分城镇之间有不相交的道路相连。道路是双向的，往返所需时间相同。金刚拥有$G$名$（G < 353535）$士兵。

由于两座城市之间的山羊奶酪走私活动日益猖獗，金刚必须在某些道路上部署士兵，使得从一座城市到另一座城市必须经过士兵。士兵不能部署在城镇内，但可以部署在道路上，且可尽可能靠近城镇。同一条道路上可部署任意数量士兵。然而，若其中一座城市遭到外国军队攻击，国王必须能够将所有士兵快速调往被攻击的城市。请帮助他部署士兵，使得这种调动时间最小化。

注意：士兵不能部署在任何城市或城镇中。两座城市的邮编分别为$95050$和$104729$，城镇的邮编范围为$0$到$N-1$。任意两个城镇或城市之间最多有一条道路。

输入

输入包含多个测试用例。每个测试用例的第一行是$N、G$和$E$$（N和G如上所述，E < 5000为道路数量）$。接下来$E$行，每行包含三个整数：$A$和$B$（道路两端的邮编），以及$φ$（通过该道路所需的时间，$φ < 1000$）。输入的最后一行是一个单独的$0$。

输出

对每个测试用例，输出可能的最小调动时间（保留一位小数）。若给定的士兵数量不足以阻止山羊奶酪走私，输出“Impossible”。

输入数据1

4 2 6
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
4 1 6
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
4 2 7
95050 0 1
0 1 2
1 104729 1
95050 2 1
2 3 3
3 104729 1
2 1 5
0

输出数据1

2.5
Impossible
3.0

来源

2005年北欧竞赛