Hide

Problem G
Horse Snatchers

There are $n$ towns in the wild west, connected via a road network. Old Man Joe wants to choose a horse to use to travel from town $1$ to town $n$. Since horses are very valuable, some towns have been overrun with gangs of horse snatchers, which steal any horses that enter the town. Any traveller that has their horse stolen will have to walk the rest of the way to their destination. Joe wants to choose the slowest horse that will still allow him to reach town $n$ on time.

Input

The first line of input contains three space-separated integers $n$, $k$ and $m$, $2 \leq n \leq 10^3$, $0 \leq k \leq n$, $1 \leq m \leq 10^5$, where $n$ is the number of towns, $k$ is the number of towns containing horse snatchers, and $m$ is the number of roads.

The next line of input contains two integers $T$ and $w$, $1 \leq T \leq 10^6$, $1 \leq w \leq 5$, where $T$ is the amount of time (in hours) Joe has to travel to town $n$, and $w$ is his walking speed in km/h.

The next line of input contains $k$ distinct space-separated integers $s_1, \dots , s_ k$, $1 \leq s_1, \dots , s_ k \leq n$, the towns that contain horse snatchers.

The final $m$ lines of input each contain three space-separated integers $a$, $b$, and $d$, $1 \leq a, b \leq n$, $a \neq b$, $1 \leq d \leq 10^4$, indicating that there is a (bidirectional) road between towns $a$ and $b$ of length $d$ km. It is guaranteed that there is a sequence of roads connecting town $1$ to town $n$, and that at most one road connects any two towns.

Output

A single line containing a real number $v$, the minimum speed in km/h Old Man Joe’s horse needs to have in order for him to travel from town $1$ to town $n$ within $T$ hours (answers within $10^{-6}$ absolute or relative error are accepted). If $v \leq w$ (meaning Joe can reach town $n$ within $T$ hours just by walking) output “No horse needed!” instead. If he can’t reach town $n$ within $T$ hours regardless of his horse’s speed, output “Impossible”.

Sample Input 1 Sample Output 1
4 1 4
3 1
2
1 2 1
1 3 6
2 4 4
3 4 9
5.0
Sample Input 2 Sample Output 2
3 0 2
4 1

1 2 1
2 3 3
No horse needed!
Sample Input 3 Sample Output 3
3 1 2
4 1
2
1 2 1
2 3 4
Impossible

Please log in to submit a solution to this problem

Log in