Problem:


 Princess in Danger 

 お姫様の危機 

English text is not available in this practice contest.

ある貧乏な国のおてんばで勇敢なお姫様が，政略結婚のため別の国に嫁ぐことになった．ところが，お姫様を亡き者としようとしている悪漢に嫁ぎ先への道中で襲われお姫様が大けがをしてしまい，近くの病院に搬送された．ところが，悪漢はお姫様は確実に亡き者とするため特殊な毒を使っていた．そのため，お姫様を助けるには本国から特別な薬と冷凍された肉親の血液を大急ぎで運ばなければならなくなった．

この血液は冷凍状態で輸送されるのだが，鮮度を保つため，前回の冷凍から最大 M 分以内に血液冷凍施設で再冷凍しなければならない．しかし，冷凍施設が設置されている場所は数カ所しかない．

血液は，十分に冷凍した状態から，再冷凍なしで M 分の間無事である．再冷凍しなくてすむ残り時間が S 分のときに，T 分間冷凍しないで輸送した場合，再冷凍しなくてすむ残り時間は S - T 分となる．再冷凍しなくてすむ残り時間は，再冷凍することにより，最大 M 分まで回復する．血液の再冷凍にかかる時間は，どれだけ冷凍するかに依存する．血液を冷凍施設で，1分冷凍するごとに再冷凍しなくてすむ残り時間は1分回復する．

本国の首都を出発する時点の，血液を再冷凍しなくてすむ残り時間はM分である．

お姫様の従者であるあなたは，大切な主君の命を救うため，本国の首都からお姫様が搬送された病院まで血液の鮮度を保ったまま輸送するための経路を計算しなければならない．そう，あなたの使命は，本国の首都からその病院への最短経路を割り出し，その最短時間を求めることである．

Input

入力は，複数のデータセットより構成される．各データセットの最初の行には，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 個の非負の整数が 1 つの空白で区切られて与えられる．これらは，冷凍施設がある町の番号を表す．なお，本国の首都とお姫様が搬送された病院はこのリストには含まれないが，冷凍施設があるものと考えて良い．続く K 行では，町と町を結ぶ道路の情報が与えられる．その第 i 行目では，3 つの非負の整数 X ，Y ，T が 1 つの空白で区切られて与えられ，これは町 X と町 Y を直接結ぶ道があり，移動には時間 T を要するということを表す．なお，この道は双方向に通行可能である．また，町Xと町Yを直接結ぶ道は高々一つしか無い．

入力は N = M = L = K = A = H = 0 の時に終了し，これはデータセットに含まれない．

Output

各データセットについて，鮮度を保ったまま血液を届けることができる最短時間を出力せよ．もし届けることができない場合には "Help!" と出力せよ．

Sample 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

Output for the Sample Input

Help!
3
2
10
5
12



Sample 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


Sample output:
Help!
3
2
10
5
12

Submission status: Runtime Error

Solution code:
town = []
freezer = []
dp = []
dic = {}
mint = 100000000
N = M = L = K = A = H = 0


def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               

while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
town = []
freezer = []
dp = []
dic = {}
mint = 100000000
N = M = L = K = A = H = 0


def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               

while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
town = []
freezer = []
dp = []
dic = {}
mint = 100000000
N = M = L = K = A = H = 0


def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, time = nt
        tt = t - time
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + time:
                    dp[tt][town] = dp[t][r] + time
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + time:
                        dp[tt + j][town] = dp[t][r] + j + time
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               

while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    if L > 0:
        freezer = list(map(int, list(input().split())))
    else:
        input()
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
town = []
freezer = []
dp = []
dic = {}
mint = 100000000
N = M = L = K = A = H = 0


def nexttown():
    for r in range(0, N):
        dic[r] = [t[1:3] for t in town if t[0] == r] + [ [t[0], t[2]] for t in town if t[1] == r]

def solve():
    solve2(A, M, 0)
    if mint == 100000000:
        return "Help!"
    return mint

def solve2(r, t, lv):
    global mint
    ntown = dic[r]
    for nt in ntown:
        town, ti = nt
        tt = t - ti
        if tt >= 0:
            if not(town in freezer):
                if dp[tt][town] == 0 or min(dp[tt][town], mint) > dp[t][r] + ti:
                    dp[tt][town] = dp[t][r] + ti
                    if town != H:
                        solve2(town, tt, lv + 1)
                    elif mint > dp[tt][town]:
                        mint = dp[tt][town]
            else:
                for j in range(M - tt, -1, -1):
                    if dp[tt + j][town] == 0 or min(dp[tt + j][town], mint) > dp[t][r] + j + ti:
                        dp[tt + j][town] = dp[t][r] + j + ti
                        if town != H:
                            solve2(town, tt + j, lv + 1)
                        elif mint > dp[tt + j][town]:
                            mint = dp[tt + j][town]
               

while True:
    town = []
    freezer = []
    dp = []
    dic = {}
    mint = 100000000
    line = input()
    N, M, L, K, A, H = map(int, line.split())
    if N == 0 and M == 0 and L == 0:
        break
    freezer = list(map(int, list(input().split())))
    for _ in range(0, K):
        t = list(map(int, list(input().split())))
        town.append(t)
    dp = [ [0] * N for _ in range(0, M + 1) ]  
    nexttown()
    print(solve())

Submission status: Runtime Error

Solution code:
inf = 1 << 28
def dfs(s,m,path):
    global ans
    if s == H:
        tmp = sum(d[i][j] for i,j in zip(path,path[1:]))
        ans = min(ans, tmp+max(0,tmp-M))
    if s in cold: m = M
    for t in range(N):
        if d[s][t] <= m:
            if path.count(t) > 2: continue
            dfs(t,m-d[s][t],path+[t])

while 1:
    N,M,L,K,A,H = map(int,raw_input().split())
    if N == 0: break
    cold = []
    if L > 0: cold += map(int,raw_input().split())
    d = [[inf]*N for i in xrange(N)]
    for loop in xrange(K):
        x,y,t = map(int,raw_input().split())
        d[x][y] = d[y][x] = t
    
    ans = inf
    dfs(A,M,[A])
    print ans if ans < inf else "Help!"

Submission status: Runtime Error

Solution code:
inf = 1 << 28
def dfs(s,m,path):
    global ans
    if s == H:
        tmp = sum(d[i][j] for i,j in zip(path,path[1:]))
        ans = min(ans, tmp+max(0,tmp-M))
    if s in cold: m = M
    for t in range(N):
        if d[s][t] <= m:
            if path.count(t) > 1: continue
            dfs(t,m-d[s][t],path+[t])

while 1:
    N,M,L,K,A,H = map(int,raw_input().split())
    if N == 0: break
    cold = map(int,raw_input().split())
    d = [[inf]*N for i in xrange(N)]
    for loop in xrange(K):
        x,y,t = map(int,raw_input().split())
        d[x][y] = d[y][x] = t
    
    ans = inf
    dfs(A,M,[A])
    print ans if ans < inf else "Help!"

Submission status: Runtime Error

Solution code:
inf = 1 << 28
while 1:
    N,M,L,K,A,H = map(int,raw_input().split())
    if N == 0: break
    cold = map(int,raw_input().split())
    d = [[inf]*N for i in xrange(N)]
    for loop in xrange(K):
        x,y,t = map(int,raw_input().split())
        d[x][y] = d[y][x] = t
    
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])

    ans = d[A][H] if d[A][H] <= M else inf
    used = [False]*N
    used[A] = True
    que = [[i,d[A][i]] for i in xrange(N) if i in cold and d[A][i] <= M]
    while que:
        s,time = que.pop(0)
        used[s] = True
        if d[s][H] <= M:
            time += d[s][H]
            ans = min(ans, time+max(0,time-M))
            continue
        for t in xrange(N):
            if t in cold and not used[t] and d[s][t] <= M:
                que.append([t,time+d[s][t]])
                
    print ans if ans < inf else "Help!"

Submission status: Runtime Error

Solution code:
inf = 1 << 28
while 1:
    N,M,L,K,A,H = map(int,raw_input().split())
    if N == 0: break
    cold = map(int,raw_input().split())
    d = [[inf]*N for i in xrange(N)]
    for loop in xrange(K):
        x,y,t = map(int,raw_input().split())
        d[x][y] = d[y][x] = t
    
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])

    ans = d[A][H] if d[A][H] <= M else inf
    used = [False]*N
    used[A] = True
    que = [[i,d[A][i]] for i in xrange(N) if i in cold and d[A][i] <= M]
    while que:
        s,time = que.pop(0)
        if time >= ans: continue
        used[s] = True
        if d[s][H] <= M:
            time += d[s][H]
            ans = min(ans, time+max(0,time-M))
            continue
        for t in xrange(N):
            if t in cold and not used[t] and d[s][t] <= M:
                que.append([t,time+d[s][t]])
                
    print ans if ans < inf else "Help!"

Submission status: Runtime Error

Solution code:
inf = 1 << 28
while 1:
    N,M,L,K,A,H = map(int,raw_input().split())
    if N == 0: break
    cold = map(int,raw_input().split())
    d = [[inf]*N for i in xrange(N)]
    for loop in xrange(K):
        x,y,t = map(int,raw_input().split())
        d[x][y] = d[y][x] = t
    
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])

    ans = d[A][H] if d[A][H] <= M else inf
    used = [False]*N
    used[A] = True
    que = [[i,d[A][i]] for i in xrange(N) if i in cold and d[A][i] <= M]
    for i,time in que: used[i] = True
    while que:
        s,time = que.pop(0)
        used[s] = True
        if d[s][H] <= M:
            time += d[s][H]
            ans = min(ans, time+max(0,time-M))
            continue
        for t in xrange(N):
            if t in cold and not used[t] and d[s][t] <= M:
                que.append([t,time+d[s][t]])
                
    print ans if ans < inf else "Help!"

Submission status: Runtime Error

Solution code:
import copy
inf = 1 << 28
while 1:
    N,M,L,K,A,H = map(int,raw_input().split())
    if N == 0: break
    cold = set(map(int,raw_input().split()))
    d = [[inf]*N for i in xrange(N)]
    for loop in xrange(K):
        x,y,t = map(int,raw_input().split())
        d[x][y] = d[y][x] = t
    
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])

    ans = d[A][H] if d[A][H] <= M else inf
    used = [False]*N
    used[A] = True
    que = sorted([[d[A][i],i] for i in xrange(N) if i in cold and d[A][i] <= M])
    for time,i in que: used[i] = True
    while que:
        nque = []
        time,s = que.pop(0)
        if time >= ans: continue
        used[s] = True
        if d[s][H] <= M:
            time += d[s][H]
            ans = min(ans, time+max(0,time-M))
            break
        for t in xrange(N):
            if t in cold and not used[t] and d[s][t] <= M:
                nque.append([time+d[s][t],t])
        que = copy.deepcopy(sorted(nque))
    print ans if ans < inf else "Help!"

Submission status: Runtime Error

Solution code:
import copy
inf = 1 << 28
while 1:
    N,M,L,K,A,H = map(int,raw_input().split())
    if N == 0: break
    cold = set(map(int,raw_input().split()))
    d = [[inf]*N for i in xrange(N)]
    for loop in xrange(K):
        x,y,t = map(int,raw_input().split())
        d[x][y] = d[y][x] = t
    
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])

    ans = d[A][H] if d[A][H] <= M else inf
    if ans < inf:
        print ans
        continue
    used = [False]*N
    used[A] = True
    que = sorted([[d[A][i],i] for i in xrange(N) if i in cold and d[A][i] <= M])
    for time,i in que: used[i] = True
    while que:
        nque = []
        time,s = que.pop(0)
        if time >= ans: continue
        used[s] = True
        if d[s][H] <= M:
            time += d[s][H]
            ans = min(ans, time+max(0,time-M))
            break
        for t in xrange(N):
            if t in cold and not used[t] and d[s][t] <= M:
                nque.append([time+d[s][t],t])
        que = copy.deepcopy(sorted(nque))
    print ans if ans < inf else "Help!"

Submission status: Runtime Error

Solution code:
def warshall(A):
    n = len(A)
    for k in xrange(n):
        for i in xrange(n):
            for j in xrange(n):
                A[i][j] = min(A[i][j], A[i][k]+A[k][j])
    return A
    
inf = 1 << 28
while 1:
    N,M,L,K,A,H = map(int,raw_input().split())
    if N == 0: break
    cold = map(int,raw_input().split())
    d = [[inf]*N for i in xrange(N)]
    for loop in xrange(K):
        x,y,t = map(int,raw_input().split())
        d[x][y] = d[y][x] = t
    
    d = warshall(d)
    
    dd = [[inf]*(L+2) for i in xrange(L+2)]
    for i in range(L):
        dd[ 0][i+1] = dd[i+1][ 0] = d[A][cold[i]] if d[A][cold[i]] <= M else inf
        dd[-1][i+1] = dd[i+1][-1] = d[H][cold[i]] if d[H][cold[i]] <= M else inf
    for i in range(L):
        for j in range(L):
            dd[i+1][j+1] = d[cold[i]][cold[j]] if d[cold[i]][cold[j]] <= M else inf
            
    dd = warshall(dd)
    time = dd[0][-1]
    print time+max(0,time-M) if time < inf else "Help!"

Submission status: Runtime Error

Solution code:
import sys

def warshall(n, matrix):
  for i in xrange(n):
    matrix[i][i] = 0
  for i in xrange(n):
    for j in xrange(n):
      for k in xrange(n):
        matrix[j][k] = min(matrix[j][k], matrix[j][i]+matrix[i][k])
  return matrix

def dijkstra(nodes, start, matrix):
  defnode = [False] * (nodes)
  cost = [sys.maxint] * (nodes)
  cost[start] = 0
  node = start
  counter = 0
  while True:
    counter += 1
    if counter == nodes or node == sys.maxint:
      return cost
    defnode[node] = True
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    node = minnode

while True:
  # N : number of towns
  # M : time limit
  # L : locations for freeze
  # K : number of roads
  # A : start
  # H : destination
  N,M,L,K,A,H = map(int, raw_input().split())
  if N==M==L==K==A==H==0: break
  if L == 0:
    l = []
  else:
    l = map(int, raw_input().split())
  matrix = [[1000000] * N for _ in xrange(N)]
  for _ in xrange(K):
    x,y,t = map(int, raw_input().split())
    matrix[x][y] = t
    matrix[y][x] = t
  costs = warshall(N, matrix)
  newmatrix = [[1000000] * (L+2) for _ in xrange(L+2)]
  nodes = []
  nodes.append(A)
  nodes.extend(l)
  nodes.append(H)
  for i in xrange(len(nodes)):
    for j in xrange(len(nodes)):
      newmatrix[i][j] = matrix[nodes[i]][nodes[j]]
      if newmatrix[i][j] > M:
        newmatrix[i][j] = 1000000
  newcosts = dijkstra(L+2, 0, newmatrix)
  cost = newcosts[L+1]
  if cost >= 1000000:
    print "Help!"
  else:
    if cost > M:
      print cost*2-M
    else:
      print cost

Submission status: Runtime Error

Solution code:
import sys

def warshall(n, matrix):
  for i in xrange(n):
    matrix[i][i] = 0
  for i in xrange(n):
    for j in xrange(n):
      for k in xrange(n):
        matrix[j][k] = min(matrix[j][k], matrix[j][i]+matrix[i][k])
  return matrix

def dijkstra(nodes, start, matrix):
  defnode = [False] * (nodes)
  cost = [sys.maxint] * (nodes)
  cost[start] = 0
  node = start
  counter = 0
  while True:
    counter += 1
    if counter == nodes or node == sys.maxint:
      return cost
    defnode[node] = True
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    node = minnode

while True:
  # N : number of towns
  # M : time limit
  # L : locations for freeze
  # K : number of roads
  # A : start
  # H : destination
  N,M,L,K,A,H = map(int, raw_input().split())
  if N==M==L==K==A==H==0: break
  l = map(int, raw_input().split())
  matrix = [[1000000] * N for _ in xrange(N)]
  for _ in xrange(K):
    x,y,t = map(int, raw_input().split())
    matrix[x][y] = t
    matrix[y][x] = t
  costs = warshall(N, matrix)
  newmatrix = [[1000000] * (L+2) for _ in xrange(L+2)]
  nodes = []
  nodes.append(A)
  nodes.extend(l)
  nodes.append(H)
  for i in xrange(len(nodes)):
    for j in xrange(len(nodes)):
      newmatrix[i][j] = matrix[nodes[i]][nodes[j]]
      if newmatrix[i][j] > M:
        newmatrix[i][j] = 1000000
  newcosts = dijkstra(L+2, 0, newmatrix)
  cost = newcosts[L+1]
  if cost >= 1000000:
    print "Help!"
  else:
    if cost > M:
      print cost*2-M
    else:
      print cost

Submission status: Runtime Error

Solution code:
import sys
import heapq

class Dijkstra(object):
  def dijkstra(self, adj, start, goal=None):
    num = len(adj)
    dist = [sys.maxint] * num
    prev = [sys.maxint] * num
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if dist[src] < prov_cost: continue
      for dest in range(num):
        cost = adj[src][dest]
        if cost != sys.maxint and dist[dest] > dist[src] + cost:
          dist[dest] = dist[src] + cost
          heapq.heappush(q, (dist[dest], dest))
          prev[dest] = src
    if goal is not None:
      return self.get_path(goal, prev)
    else:
      return dist

  def get_path(self, goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != sys.maxint:
      path.append(prev[dest])
      dest = prev[dest]
    return list(reversed(path))

while True:
  N,M,L,K,A,H=map(int,raw_input().split())
  if N==0: break
  # t(n,t) : minimum cost to remain t times and reach town n
  if L==0:
    Ls=[]
  else:
    Ls=map(int,raw_input().split())
  edge=[[sys.maxint]*(N*(M+1)) for _ in xrange(N*(M+1))]
  for l in Ls:
    for i in xrange(M):
      edge[l*(M+1)+i][l*(M+1)+i+1]=1
  for _ in xrange(K):
    s,g,c=map(int,raw_input().split())
    for i in xrange(c,M+1):
      edge[s*(M+1)+i][g*(M+1)+i-c]=c
      edge[g*(M+1)+i][s*(M+1)+i-c]=c
  cost=Dijkstra().dijkstra(edge, A*(M+1)+M)
  minCost=sys.maxint
  for i in xrange(M+1):
    minCost=min(minCost,cost[H*(M+1)+i])
  if minCost==sys.maxint: print "Help!"
  else: print minCost

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
while 1:
    N, M, L, K, A, H = map(int, raw_input().split())
    if N == 0:
        break
    F = [0]*N
    if L>0:
        for e in map(int, raw_input().split()):
            F[e] = 1
    G = [[] for i in xrange(N)]
    for i in xrange(K):
        x, y, t = map(int, raw_input().split())
        G[x].append((y, t))
        G[y].append((x, t))
    dist = [[10**18]*(M+1) for i in xrange(N)]
    dist[A][M] = 0
    que = [(0, A, M)]
    while que:
        cost, v, rest = heappop(que)
        if dist[v][rest] < cost:
            continue
        if F[v] and rest < M and cost + 1 < dist[v][rest+1]:
            dist[v][rest+1] = cost+1
            heappush(que, (cost+1, v, rest+1))
        for t, co in G[v]:
            if rest>=co and cost + co < dist[t][rest-co]:
                dist[t][rest-co] = cost + co
                heappush(que, (cost+co, t, rest-co))
    ans = min(dist[H])
    print "Help!" if ans > 10**17 else ans

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        N,M,L,K,A,H = LI()
        if N == 0:
            break
        S = set()
        if L > 0:
            S = set(LI())
        e = collections.defaultdict(list)
        for _ in range(K):
            a,b,d = LI()
            e[a].append((b,d))
            e[b].append((a,d))

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[(-M,s)] = 0
            q = []
            heapq.heappush(q, (0, -M, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, m, u = heapq.heappop(q)
                if v[(m,u)]:
                    continue
                for mm in range(m,1):
                    v[(mm,u)] = True

                for uv, ud in e[u]:
                    if ud > -m or v[(m+ud,uv)]:
                        continue
                    vd = k + ud
                    vm = m+ud
                    if uv in S:
                        vm = -M
                    if d[(vm,uv)] > vd:
                        for mm in range(vm,1):
                            d[(mm,uv)] = vd
                        heapq.heappush(q, (vd, vm, uv))

            return d

        d = search(A)
        r = inf
        for k in list(d.keys()):
            if k[1] == H and r > d[k]:
                r = d[k]
        if r == inf:
            rr.append('Help!')
        elif r <= M:
            rr.append(r)
        else:
            rr.append(r*2-M)

    return '\n'.join(map(str,rr))


print(main())