위험에 빠진 공주

어느 가난한 나라의 말괄량이 용감한 공주가 정략 결혼을 위해 다른 나라로 시집을 가게 되었다. 그런데 공주를 죽이려는 악당이 시집으로 가는 길에 습격해 공주가 크게 다쳤고, 근처 병원으로 옮겨졌다. 악당은 공주를 확실히 죽이기 위해 특수한 독을 사용했다. 그래서 공주를 살리려면 본국에서 특별한 약과 냉동된 친족의 혈액을 급히 운반해야 한다.

이 혈액은 냉동 상태로 수송되는데, 신선도를 유지하려면 지난 냉동으로부터 최대 M분 이내에 혈액 냉동 시설에서 다시 냉동해야 한다. 그러나 냉동 시설이 설치된 곳은 몇 군데뿐이다.

혈액은 충분히 냉동된 상태에서 다시 냉동하지 않고 M분 동안 버틴다. 다시 냉동하지 않고 버틸 수 있는 남은 시간이 S분일 때 T분 동안 냉동하지 않고 수송하면, 다시 냉동하지 않고 버틸 수 있는 남은 시간은 S - T분이 된다. 다시 냉동하면 남은 시간은 최대 M분까지 회복된다. 혈액을 다시 냉동하는 데 걸리는 시간은 얼마나 냉동하는지에 따라 다르다. 냉동 시설에서 혈액을 1분 냉동할 때마다 다시 냉동하지 않고 버틸 수 있는 남은 시간이 1분 회복된다.

본국의 수도에서 출발하는 시점에 혈액이 다시 냉동 없이 버틸 수 있는 남은 시간은 M분이다.

공주의 시종인 당신은 소중한 주군의 목숨을 구하기 위해 본국의 수도에서 공주가 옮겨진 병원까지 혈액의 신선도를 유지한 채 수송할 경로를 계산해야 한다. 그렇다. 당신의 임무는 본국의 수도에서 그 병원까지의 최단 경로를 찾아 그 최단 시간을 구하는 것이다.

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트의 첫 줄에는 6개의 음이 아닌 정수 N(2 ≦ N ≦ 100), M(1 ≦ M ≦ 100), L(0 ≦ L ≦ N - 2), K, A(0 ≦ A ＜ N), H(0 ≦ H ＜ N)가 주어진다. 이들은 각각 도시의 수, 다시 냉동하기까지의 제한 시간, 냉동 시설이 있는 도시의 수, 도시와 도시를 직접 잇는 도로의 수, 본국의 수도 번호, 공주가 옮겨진 병원이 있는 도시 번호를 나타낸다. 본국의 수도와 공주가 옮겨진 병원은 서로 다른 도시이다. 도시에는 0부터 N-1까지의 번호가 각각 부여되어 있다. 다음 줄에는 L개의 음이 아닌 정수가 공백 하나로 구분되어 주어진다. 이들은 냉동 시설이 있는 도시의 번호를 나타낸다. 본국의 수도와 공주가 옮겨진 병원은 이 목록에 포함되지 않지만, 냉동 시설이 있는 것으로 간주해도 된다. 이어서 K개의 줄에 도시와 도시를 잇는 도로 정보가 주어진다. 그 i번째 줄에는 3개의 음이 아닌 정수 X, Y, T가 공백 하나로 구분되어 주어지며, 이는 도시 X와 도시 Y를 직접 잇는 도로가 있고 이동에 시간 T가 걸린다는 것을 나타낸다. 이 도로는 양방향으로 통행할 수 있다. 또한 도시 X와 도시 Y를 직접 잇는 도로는 많아야 하나뿐이다.

입력은 N = M = L = K = A = H = 0일 때 끝나며, 이는 데이터 세트에 포함되지 않는다.

각 데이터 세트에 대해 신선도를 유지한 채 혈액을 전달할 수 있는 최단 시간을 출력하라. 전달할 수 없으면 "Help!"를 출력하라.