Traveling by Stagecoach

Interview

Time limit3sMemory limit128 MB

Summary

With up to 8 one-use tickets, each giving a speed, find the fastest route from city a to city b, or report Impossible.

Level: Medium7 of 10
Topics: Graph, Shortest path, Bit manipulation, Dynamic programming
Solved: No attempts yet

Problem

Once upon a time, there was a traveler.

He plans to travel using stagecoaches (horse wagons). His starting point and destination are fixed, but he cannot decide his route on his own. Your job in this problem is to write a program that determines the route for him.

There are several cities in the country and a road network connecting them. If there is a road between two cities, one can travel by stagecoach from one of them to the other. A coach ticket is needed for a coach ride, and the number of horses is written on each ticket. Of course, with more horses the coach runs faster.

At the starting point, the traveler has a number of coach tickets. Considering these tickets together with the road network, you should find the best route that takes him to the destination in the shortest time. How the tickets are used must also be taken into account.

The following conditions are assumed.

A coach ride takes the traveler from one city to another directly connected by a road. In other words, on each arrival at a city he must change the coach.
Only one ticket can be used for a single coach ride between two directly connected cities.
Each ticket can be used only once.
The time needed for a coach ride is the distance between the two cities divided by the number of horses.
The time needed to change coaches is ignored.

Input

The input consists of multiple datasets, each in the following format. The last dataset is followed by a line containing five zeros separated by spaces.

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

Every input item in a dataset is a non-negative integer. If a line contains two or more items, they are separated by a space.

$n$ is the number of coach tickets, with $1 \le n \le 8$ .
$m$ is the number of cities in the network, with $2 \le m \le 30$ .
$p$ is the number of roads between cities, which may be $0$ .
$a$ is the index of the starting city and $b$ is the index of the destination city, with $a \ne b$ . Every city index in a dataset (including $a$ and $b$ ) is between $1$ and $m$ .

The second line gives the ticket details. $t_i$ is the number of horses written on the $i$ -th ticket ( $1 \le i \le n$ ), with $1 \le t_i \le 10$ .

The next $p$ lines give the road details. The $i$ -th road connects cities $x_i$ and $y_i$ and has distance $z_i$ ( $1 \le i \le p$ ), with $1 \le z_i \le 100$ .

No two roads connect the same pair of cities, and no road connects a city to itself. Each road can be traveled in both directions.

Output

For each dataset in the input, output one line as specified below. An output line must not contain any extra characters such as spaces.

If the traveler can reach the destination, output the time needed for the best route (a route that takes the shortest time), rounded to exactly three digits after the decimal point (for example, 30.000 or 3.667). The answer is always a rational number that never lands exactly on a rounding boundary, so its value rounded to three decimals is uniquely determined.

If the traveler cannot reach the destination, output the string Impossible. The destination is unreachable either when there is no route leading to it, or when the number of tickets is not sufficient. Note that the first letter of Impossible is uppercase while the remaining letters are lowercase.

Examples2

Example 1

Input

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

Expected output

30.000
3.667
Impossible
Impossible
2.856

Example 2
Input
```
1 2 1 1 2
5
1 2 10
0 0 0 0 0
```
Expected output
```
2.000
```