역마차 여행

옛날에 한 여행자가 있었다.

그는 역마차(말이 끄는 마차)를 이용해 여행을 하려고 한다. 출발지와 목적지는 정해져 있지만, 어떤 경로로 갈지는 스스로 정하지 못한다. 이 문제에서 여러분이 할 일은 그를 위해 경로를 정하는 프로그램을 작성하는 것이다.

이 나라에는 여러 도시가 있고, 도시들을 잇는 도로망이 있다. 두 도시 사이에 도로가 있으면, 역마차를 타고 한 도시에서 다른 도시로 이동할 수 있다. 마차를 한 번 타려면 승차권(티켓)이 한 장 필요하다. 각 승차권에는 말의 수가 적혀 있으며, 당연히 말이 많을수록 마차는 더 빠르게 달린다.

출발할 때 여행자는 여러 장의 승차권을 가지고 있다. 이 승차권들과 도로망 정보를 함께 고려하여, 목적지까지 가장 짧은 시간에 도착하는 최적의 경로를 찾아야 한다. 승차권을 어떻게 사용할지도 함께 고려해야 한다.

다음 조건을 가정한다.

• 한 번의 마차 이동은 도로로 직접 연결된 한 도시에서 다른 도시로 여행자를 데려간다. 즉, 어떤 도시에 도착할 때마다 마차를 갈아타야 한다.
• 도로로 직접 연결된 두 도시 사이를 한 번 이동하는 데에는 승차권 한 장만 사용할 수 있다.
• 각 승차권은 한 번만 사용할 수 있다.
• 한 번의 마차 이동에 걸리는 시간은 두 도시 사이의 거리를 말의 수로 나눈 값이다.
• 마차를 갈아타는 데 걸리는 시간은 무시한다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다. 마지막 데이터셋 다음에는 (공백으로 구분된) 다섯 개의 0으로 이루어진 줄이 온다.

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

데이터셋의 모든 입력 항목은 음이 아닌 정수이다. 한 줄에 항목이 둘 이상 있으면 공백으로 구분된다.

• $n$은 승차권의 수이며 $1 \le n \le 8$이다.
• $m$은 도로망에 있는 도시의 수이며 $2 \le m \le 30$이다.
• $p$는 도시 사이를 잇는 도로의 수이며 $0$일 수도 있다.
• $a$는 출발 도시의 번호, $b$는 목적 도시의 번호이며 $a \ne b$이다. 데이터셋에 나오는 모든 도시 번호($a$, $b$ 포함)는 $1$ 이상 $m$ 이하이다.

둘째 줄은 승차권 정보를 준다. $t_i$는 $i$번째 승차권에 적힌 말의 수이며($1 \le i \le n$), $1 \le t_i \le 10$이다.

이어지는 $p$개의 줄은 도로 정보를 준다. $i$번째 도로는 도시 $x_i$와 $y_i$를 잇고 거리 $z_i$를 가지며($1 \le i \le p$), $1 \le z_i \le 100$이다.

같은 도시 쌍을 잇는 도로는 둘 이상 존재하지 않으며, 도로가 한 도시를 자기 자신과 잇는 일도 없다. 각 도로는 양방향으로 이동할 수 있다.

각 데이터셋마다 아래 규정에 따라 한 줄을 출력한다. 출력 줄에는 공백과 같은 불필요한 문자가 있어서는 안 된다.

여행자가 목적지에 도달할 수 있으면, 최적 경로(가장 짧은 시간이 걸리는 경로)에 필요한 시간을 소수점 아래 정확히 셋째 자리까지 반올림하여 출력한다(예: 30.000, 3.667). 이 문제에서 답은 항상 유리수이며 반올림 경계에 정확히 놓이는 경우가 없으므로, 셋째 자리 반올림 값은 유일하게 정해진다.

여행자가 목적지에 도달할 수 없으면 문자열 Impossible을 출력한다. 목적지로 가는 경로가 아예 없거나 승차권의 수가 부족한 경우 모두 도달할 수 없는 경우에 해당한다. Impossible의 첫 글자는 대문자이고 나머지 글자는 소문자임에 유의하라.