以下题面由 AI 翻译。

问题描述

从前，有一位旅行者打算乘坐马车进行旅行。他的起点和目的地是固定的，但他无法确定路线。你的任务是编写一个程序，为他确定最佳路线。

该国拥有若干城市，由道路网络连接。若两城市间有道路，则可乘坐马车直接往返。每次乘坐需要一张车票，车票上标有马匹数量。马匹越多，马车行驶越快。

旅行者在起点持有若干车票。根据这些车票和道路网络信息，你需要找到一条最快到达目的地的路线，并考虑车票的使用情况。

条件说明：

• 每次乘坐马车必须在直接相连的两城市间移动，到达城市后必须更换马车。
• 两城市间的每次乘坐只能使用一张车票。
• 每张车票仅可使用一次。
• 乘坐时间等于道路距离除以马匹数。
• 换乘时间忽略不计。

输入格式

输入包含多个数据集，每个数据集格式如下。最后一个数据集后跟一行五个零（空格分隔）。

n m p a b
t1 t2 ... tn
x1 y1 z1
x2 y2 z2
...
xp yp zp

所有数据均为非负整数。若一行有多个数据项，以空格分隔。

• n 是车票数量，范围 [1, 8]。
• m 是城市数量，范围 [2, 30]。
• p 是道路数量，可能为 0。
• a 是起点城市编号，b 是终点城市编号，a ≠ b。所有城市编号在 [1, m] 范围内。
• 第二行给出车票详情，ti 表示第 i 张车票的马匹数，范围 [1, 10]。
• 后续 p 行描述道路：城市 xi 与 yi 间有一条长度为 zi 的双向道路，距离范围 [1, 100]。无重复道路或自环。

输出格式

对每个数据集，输出一行：

• 若可达，输出最短时间（误差 ≤ 0.001）。可输出任意位数小数，但需满足精度。
• 若不可达（无路线或车票不足），输出 Impossible。

样例输入

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

注意：小数点后位数不唯一，例如 30.0 或 3.66667 均可接受。

数据范围与提示

• 车票使用限制：必须按道路逐段使用车票，不可重复使用。
• 道路网络：可能存在不连通的情况，需考虑无法到达的场景。
• 动态规划：建议使用状态压缩 DP 处理车票使用状态。