描述

很久很久以前，有一位旅行者。

他计划乘坐驿马车（马车）旅行。他的起点和目的地是固定的，但他无法确定自己的路线。你在这个问题中的工作是编写一个程序来为他确定路线。

该国有几个城市，并有公路网络连接它们。如果两个城市之间有一条路，可以乘坐驿马车从其中一个城市到另一个城市。乘坐长途汽车需要长途汽车票。每张门票中都指定了马匹的数量。当然，马匹越多，马车跑得越快。

在起点，旅行者有很多车票。通过考虑这些票和道路网络上的信息，您应该找到在最短的时间内将他带到目的地的最佳路线。应考虑长途汽车票的使用。

假设满足以下条件：

1. 乘坐长途汽车将旅行者从一个城市带到另一个由公路直接连接的城市。换句话说，每次到达一个城市时，他都必须换车。
2. 两张公路直连城市之间的长途汽车只能使用一张车票。
3. 每张票券只能使用一次。
4. 乘坐长途汽车所需的时间是两个城市之间的距离除以马匹的数量。
5. 更换车厢所需的时间应该忽略不计。

---

输入

输入由多个数据集组成，每个数据集采用以下格式。最后一个数据集后跟一行，其中包含 $5$ 个 $0$（用空格分隔）。

$n$ $m$ $p$ $a$ $b$

$t1$ $t2$ ... $tn$

$x1$ $y1$ $z1$

$x2$ $y2$ $z2$

...

$xp$ $yp$ $zp$

数据集中的每个输入项都是非负整数。如果一行包含两个或多个输入项，则它们之间用空格分隔。

• $n$ 是长途汽车票的数量。您可以假设票证的数量介于 $1$ 到 $8$ 之间。
• $m$ 是网络中的城市数。您可以假设城市数量介于 $2$ 到 $30$ 之间。
• $p$ 是城市之间的道路数，可能为零。
• $a$ 是起始城市的城市索引。
• $b$ 是目标城市的城市索引。$a$ 不等于 $b$。您可以假设数据集中的所有城市索引（包括上述两个索引）都在 $1$ 和 $m$ 之间。

数据集的第二行给出了长途汽车票的详细信息。$t_i$ 是第 $i$ 张马车票中指定的马匹数（$1 \leq i \leq n$）。您可以假设马的数量介于 $1$ 到 $10$ 之间。

以下 $p$ 行给出了城市之间道路的详细信息。第 $i$ 条路连接两个城市，城市索引为 $x_i$ 和 $y_i$，距离为 $z_i$（$1 \leq i \leq p$）。您可以假设距离介于 $1$ 和 $100$ 之间。

没有两条道路连接同一对城市。道路永远不会将城市与自身连接起来。每条道路都可以双向行驶。

---

输出

对于输入中的每个数据集，应输出一行，如下所示。输出行不应包含额外的字符，例如空格。

• 如果旅客可以到达目的地，则应打印最佳路线（时间最短的路线）所需的时间。答案的误差不应大于 $0.001$。只要满足上述精度条件，您可以在小数点后输出任意数量的数字。
• 如果旅行者无法到达目的地，则应打印字符串 Impossible。当没有通往目的地的路线或车票数量不足时，人们无法到达目的地。请注意，Impossible 的第一个字母是大写的，而其他字母是小写的。

---

输入数据 1

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

输出数据 1

30.000
3.667
Impossible
Impossible
2.856

---

提示

由于未指定小数点后的位数，因此上述结果并不是唯一的解决方案。例如，以下结果也是可以接受的：

30.0
3.66667
Impossible
Impossible
2.85595

---

来源

日本 2005 国内

---