Đề bài

Có N thành phố, M con đường hai chiều, mỗi con đường có độ dài w. Một số thành phố có trạm sạc xe điện. Xe xuất phát từ thành phố s, muốn đến thành phố t với bình điện dung lượng tối đa C (không thể đi quãng đường dài hơn C giữa hai lần sạc). Khi đến một thành phố có trạm sạc, xe được sạc đầy. Hỏi tổng quãng đường ngắn nhất để đi từ s đến t, hoặc in -1 nếu không thể.

Dữ liệu vào

\(N, M, K, C ( 1 \le N \le 10^5, 1 \le M \le 2 * 10^5, 0 \le K \le N, 1 \le C \le 10^9)\)

Dòng tiếp: K số nguyên khác nhau là các thành phố có trạm sạc

Dòng tiếp: \(s, t (1 \le s, t \le N)\)

M dòng sau: \(u,v,w (1 \le u , v \le N, 1 \le w \le 10^9)\)

Dữ liệu ra

Một số nguyên: độ dài đường đi ngắn nhất, hoặc -1.

Ví dụ