Princess in Danger (AOJ 2021) by letter
Contest: 3575    RunID: 2377841    Status: Accepted    Date: Sun Jun 18 20:35:50 JST 2017


#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;

#define DEBUG false

int main() {
	
	ll n, m, l, k, a, h;
	//a:首都
	//h:目的地
	while(cin >> n >> m >> l >> k >> a >> h){
		if(n == 0 && m == 0 && l == 0 && k == 0 && a == 0 && h == 0) break;
	
		vector<bool> cold(n);
		vector<vector<ii>> g(n);
		rep(i, l){
			int tmp;
			cin >> tmp;
			cold[tmp] = true;
		}
		rep(i, k) {
			ll x, y, k;
			cin >> x >> y >> k;
			g[x].push_back(make_pair(y, k));
			g[y].push_back(make_pair(x, k));
		}
		
		vector<vector<bool>> used(n, vector<bool>(m+1, false));
		priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>> > qu;//cost, now, rest
		qu.push(make_pair(0, make_pair(a, m)));
		bool flag = false;
		while(!qu.empty()){
			auto tmp = qu.top();
			qu.pop();
			ll cost = tmp.first;
			ll pos = tmp.second.first;
			ll rest = tmp.second.second;
			if(used[pos][rest]) continue;
			used[pos][rest] = true;
			if(DEBUG) cout << cost << "\t" << pos << endl;
			if(pos == h){
				flag = true;
				cout << cost << endl;
				break;
			}
			
			if(cold[pos] && rest < m) qu.push(make_pair(cost+1, make_pair(pos, rest+1)));
			rep(i, g[pos].size()){
				ll weight = g[pos][i].second;
				if(DEBUG) cout << g[pos][i].first << "\t" << rest << "\t" << weight << endl;
				if(rest - weight >= 0) qu.push(make_pair(cost + weight, make_pair(g[pos][i].first, rest-weight)));
			}
			
		}
		
		if(!flag) cout << "Help!" << endl;
		
	}
	
	
	return 0;
}