Princess in Danger

Time limit8sMemory limit512 MB

Summary

Given a graph with towns that can refreeze blood, find the minimum travel time from the capital to the hospital so the blood never stays unfrozen longer than M minutes.

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

Problem

A tomboyish and brave princess of a poor country is to be married off to another country for political reasons. On the way to her new home, a villain who wants her dead attacks her, leaving her badly injured, and she is taken to a nearby hospital. The villain used a special poison to make sure she dies. To save her, a special medicine and frozen blood from a relative must be rushed from her home country.

The blood is transported frozen, but to keep it fresh it must be refrozen at a blood-freezing facility within at most M minutes of the previous freezing. However, only a few places have freezing facilities.

Blood that is fully frozen stays usable for M minutes without refreezing. If the remaining time before refreezing is S minutes and the blood is transported for T minutes without refreezing, the remaining time before refreezing becomes S - T minutes. Refreezing restores the remaining time up to M minutes. The time required to refreeze blood depends on how much it is frozen. For every 1 minute the blood is frozen at a freezing facility, the remaining time before refreezing is restored by 1 minute.

At the moment of departure from the capital of the home country, the remaining time before the blood must be refrozen is M minutes.

As the princess's attendant, you must compute a route to transport the blood from the capital of the home country to the hospital where the princess was taken while keeping it fresh, in order to save your precious lord's life. Yes, your mission is to find the shortest route from the capital of the home country to that hospital and determine the shortest time.

Input

The input consists of multiple datasets. The first line of each dataset contains six non-negative integers N(2 ≦ N ≦ 100), M(1 ≦ M ≦ 100), L(0 ≦ L ≦ N - 2), K, A(0 ≦ A ＜ N), H(0 ≦ H ＜ N). These represent the number of towns, the time limit before refreezing, the number of towns with a freezing facility, the number of roads directly connecting towns, the number of the capital of the home country, and the number of the town with the hospital where the princess was taken. The capital and the hospital town are different towns. Towns are numbered from 0 to N-1. The next line contains L non-negative integers separated by single spaces. These are the numbers of the towns with a freezing facility. The capital and the hospital town are not included in this list, but they may be treated as having a freezing facility. The following K lines give information about roads connecting towns. The i-th line contains three non-negative integers X, Y, T separated by single spaces, meaning there is a road directly connecting town X and town Y that takes time T to travel. This road can be traveled in both directions. There is at most one road directly connecting town X and town Y.

The input ends when N = M = L = K = A = H = 0, which is not included in the datasets.

Output

For each dataset, output the shortest time in which the blood can be delivered while keeping it fresh. If it cannot be delivered, output "Help!".

Examples1

Example 1

Input

2 1 0 1 0 1
0 1 2
3 1 1 2 0 1
2
0 2 1
1 2 1
3 2 1 2 0 1
2
0 2 1
1 2 1
4 4 1 4 1 3
2
0 1 2
1 2 4
0 2 1
3 0 3
5 3 2 6 0 3
1 2
2 1 2
1 0 1
3 4 1
2 4 1
4 1 2
2 0 2
5 4 2 6 0 3
1 2
4 2 4
2 1 2
4 3 1
0 1 5
1 4 2
2 0 3
0 0 0 0 0 0

Expected output

Help!
3
2
10
5
12