Description

有一个旅行者计划乘马车旅行，他的出 发点和目的地是固定的，但不能确定路线。全国的城市有一个公路网， 若在两个城市之间有一条路，则可以坐公共马车从一个城市到另一个城 市。乘马车需要一张票，在每张票上都注明了马的数量。当然，马越 多，马车跑得越快。在出发点，旅行者有许多车票。通过考虑这些车票 和道路网络上的信息，我们应该能找到在最短时间内把他带到目的地的 最佳路线。应考虑怎样使用车票，假设以下条件：

①乘马车可以把旅行 者从一个城市直接带到另一个通过公路相连的城市。换而言之，每到一 个城市，他都必须换车；

②在通过公路直接连接的两个城市之间只可以 使用一张车票；

③每张车票都只可以使用一次；

④乘马车所需的时间是 两个城市之间的距离除以马的数量；

⑤应忽略换乘所需的时间。

Format

Input

输入由多个数据集组成，每个数据集的格式如下。在最后 一个数据集后面是一行，包含$5$个$0$（用空格分隔）。

数据集中的每个输入项都是非负整数。n 是长途汽车票的数量， $1≤n ≤8$；$m$ 是城市数，$2≤m ≤30$；$p$ 是道路数，可能为$0$；$a$ 是起始 城市的编号，$b$ 是目的地城市的编号，$a ≠b$ 。所有城市的编号都为$1～m$。第2行给出了车票信息，$t_i$是第$i$张车票的马数$（1≤i ≤n ，1≤t_i ≤10）$。以下$p$ 行给出城市之间的道路信息。第$i$ 条道路将两个 城市$x_i$和$y_i$ 连接起来，并有距离$z_i （1≤i ≤p ，1≤z_i ≤100）$。两 个城市之间最多一条道路，一条路不会连接城市自己，每条路都可双向 行驶。

Output

若旅行者可以到达目的地，则输出出发点到目的地的最短 时间。答案的误差不应大于$0.001$。在满足上述精度条件的前提下，可 以输出小数点后的任意位数。若无法到达目的地，则输 出“Impossible”。

Samples

3 4 3 1 4
3 1 2
1 2 10
2 3 30
3 4 20
2 4 4 2 1
3 1
2 3 3
1 3 3
4 1 2
4 2 5
2 4 3 4 1
5 5
1 2 10
2 3 10
3 4 10
1 2 0 1 2
1
8 5 10 1 5
2 7 1 8 4 5 6 3
1 2 5
2 3 4
3 4 7
4 5 3
1 3 25
2 4 23
3 5 22
1 4 45
2 5 51
1 5 99
0 0 0 0 0

30.000
3.667
Impossible
Impossible
2.856

来源

POJ2686