ACM International Collegiate Programming Contest
Japan Domestic, 2005-07-01

Problem D
Traveling by Stagecoach

昔，昔のことである．一人の旅人がいた．彼は，馬車（駅馬車）を使っての旅行を計画している．出発地と目的地は決まっているのだが，ルートが決まらなくて困っている．彼のためにルートを決定するプログラムを書くことがあなたの仕事である．

この国には複数の都市があり，それらの間を結ぶ道路網が整備されている．道路で直結されている二つの都市の間は，馬車で移動することができる．馬車に乗るには，馬車券が必要である．それぞれの馬車券には，馬の頭数が指定されている．当然ながら，頭数の多い馬車ほど速い．

旅人は，出発時に何枚かの馬車券を持っている．道路網と手持ちの馬車券に関する情報から，どのようなルートを選べば最も早く目的地に着けるかを求めたい．この際，馬車券をどう使えばよいかも考える必要がある．

次のような条件を仮定する．

1台の馬車で移動できるのは，1区間（道路で直結された都市間）だけである．すなわち，都市に到着するたびに馬車を乗り換えなければならない．
1区間に使える馬車券は1枚だけである．
1枚の馬車券は一度しか使えない．
都市間の所要時間は，距離を頭数で割った値である．
乗り換えに要する時間は無視する．

Input

入力は複数のデータセットから構成される．各データセットの形式は次に示すとおりである．最後のデータセットの直後に，空白で区切られた五つの0からなる行がある．

n m p a b
t₁ t₂ ... t_n
x₁ y₁ z₁
x₂ y₂ z₂
...
x_p y_p z_p

データセットの中の入力項目は，すべて非負の整数である． 1行の中に二つ以上の入力項目がある場合の区切りは空白1個である．

nは，馬車券の枚数である． 1以上8以下と仮定してよい． mは，都市の数である． 2以上30以下と仮定してよい． pは，都市間道路の本数である．道路の本数が0のこともある．

aは，出発地の都市番号である． bは，目的地の都市番号である． aはbと等しくない．この二つを含めて，データセット中に現れる都市番号は1以上m以下と仮定してよい．

データセットの2行目は，出発時に持っている馬車券それぞれに関する情報を表す． t_iは，i番目の馬車券（1<=i<=n）に指定された頭数である．頭数は1以上10以下であると仮定してよい．

これに続くp行が都市間道路の記述である． x_iとy_iが両端の都市番号， z_iがその道路に沿った距離である（1<=i<=p）．距離は1以上100以下と仮定してよい．

ある二つの都市を結ぶ道路が2本以上存在することはない． 1本の道路の両端が同じ都市であることはない．それぞれの道路は，どちら向きの移動にも使うことができる．

Output

入力の各データセットに対して，以下に規定する結果を一つの行として出力しなさい．出力行の中に，結果を表す文字以外のもの（たとえば空白）が含まれていてはならない．

目的地に到達できる場合は，最も所要時間の短いルートを選んだ時の所要時間を出力すること．答には，0.001を越える誤差があってはいけない．この条件を守る限り，小数点以下に何個の数字を出力してもよい．

目的地に到達できない場合は，Impossibleと出力すること．これに該当するのは，到達できるルートが存在しない場合と馬車券の枚数が足りない場合である． Impossibleは，最初の文字が大文字，ほかが小文字であることに注意．

Sample 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

Output for the Sample Input

30.000
3.667
Impossible
Impossible
2.856

小数点以下の数字の個数は規定されていないので，上の出力結果が唯一の正解ではない．たとえば，次のような出力結果でも正解である．

30.0
3.66667
Impossible
Impossible
2.85595

First Input Data