여왕이 내준 퀘스트

옛날 옛적, 마법사가 프로그래머만큼 흔하던 시절, 젊은 마법 검사 아틴이 속으로 중얼거렸다. "세상에, 나 무일푼이잖아."

얼마 지나지 않아 그는 순간이동 주문을 외웠고, 제국에서 가장 높은 곳인 1번 도시의 왕궁 옥상에 떨어졌다. 시야가 탁 트여 있어서 그는 도시 N개와 양방향 도로 M개를 한눈에 확인했다. i번째 도로는 도시 Ai와 Bi를 잇고, 아틴이 이 도로를 지나는 데 Ti의 시간이 걸린다. 두 도시를 잇는 도로가 여러 개일 수 있고, 도로만으로 어느 도시에서든 다른 도시로 갈 수 있다는 보장은 없다.

3초 뒤, 차를 마시던 여왕이 그를 발견하고 K개의 퀘스트를 내렸다. i번째 퀘스트를 해결하려면 아틴이 도시 Qi에 가서 찻잎을 모아야 한다. 퀘스트가 모두 찻잎을 모으는 일이라서, 여왕은 아틴이 어떤 순서로 퀘스트를 끝내든 상관하지 않았다. 퀘스트를 모두 마치면 아틴은 왕궁으로 돌아와 여왕에게 보고해야 한다.

아틴은 마법을 세 가지 배웠다. 첫 번째는 초고속 시공 베기다. 찻잎을 순식간에 베고, 벤 찻잎을 곧바로 주머니에 옮겨 준다. 이 마법은 마나를 거의 쓰지 않는다. 도시 사이를 이동하는 데는 시간이 걸리지만, 찻잎을 모으는 과정 자체는 즉시 끝난다.

두 번째는 자기 순간이동 주문이다. 이 주문은 마나를 100% 소모한다. 이 마법도 첫 번째 마법처럼 영창과 이동이 모두 즉시 일어난다. 마나는 활동과 관계없이 저절로 회복되며, 0%에서 100%까지 회복하는 데 S의 시간이 걸린다. 마나는 100%를 넘지 않는다.

아틴은 방금 순간이동 주문을 써서 마나가 0%다. 여왕의 이야기를 듣는 것도 마나 회복에는 도움이 되지 않았다.

세 번째는 미래를 엿보고, 불운한 영혼의 명석몽에 끼어들어 프로그램을 짜게 만드는 마법이다. 지금 이 프로그램을 짜는 불운한 영혼이 바로 당신이다. 아틴이 퀘스트를 모두 완료하는 데 필요한 최소 시간을 계산하라.

첫 줄에 정수 네 개 N M K S가 주어진다 (2 ≤ N ≤ 100 000; 1 ≤ M ≤ 200 000; 1 ≤ K ≤ min(16, N-1); 1 ≤ S ≤ 10^9). 각각 도시 수, 도로 수, 퀘스트 수, 마나가 0%에서 100%까지 차는 데 걸리는 시간이다.

이어지는 M개의 줄에는 정수 세 개 Ai Bi Ti가 주어진다 (1 ≤ Ai, Bi ≤ N; Ai = Bi; 1 ≤ Ti ≤ 10^9). 도시 Ai와 도시 Bi를 잇는 i번째 양방향 도로이며, 이 도로를 지나는 데 Ti의 시간이 걸린다.

마지막 줄에는 증가하는 순서로 정렬된 정수 K개 Qi가 주어진다 (2 ≤ Qi ≤ N). i번째 퀘스트를 수행할 도시 번호이다.

한 줄에 정수 하나를 출력한다. 모든 퀘스트를 끝내고 1번 도시로 돌아오는 데 필요한 최소 시간이다.