Hệ thống giao thông thành phố Hoài Nhơn gồm ~n~ nút giao thông đánh số ~1, 2, \dots, n~ kết nối bởi ~m~ đường hai chiều, mỗi con đường tốn thời gian di chuyển nhất định, lượng thời gian này đúng với mọi phương tiện giao thông vì thành phố quy định tốc độ di chuyển cố định trong toàn hệ thống.

Trong chuyến du lịch ở thành phố Hoài Nhơn, Bờm cần di chuyển từ nút giao thông ~s~ đến nút giao thông ~t~ (~1 \le s \le n~, ~1 \le t \le n~, ~s \ne t~). Tuy nhiên, khi chuẩn bị xuất phát thì cậu mới biết: do có Đoàn ngoại giao nước ngoài đến làm việc nên một số con đường sẽ bị chặn tạm thời. Cụ thể, hành trình của Đoàn ngoại giao đi qua ~c~ nút giao thông là ~(w_1, w_2, \dots, w_c)~, hành trình này thông suốt và không có con đường nào xuất hiện quá một lần.

Đối với mỗi con đường trong hành trình, tạm kí hiệu là ~(w_i, w_j)~, kể từ khi đoàn ngoại giao xuất hiện ở ~w_i~ cho đến khi ra khỏi ~w_j~ không có phương tiện nào được phép tiến vào cả từ ~w_i~ lẫn ~w_j~ (tức là không ai được đi vào con đường này, từ bất kì đầu nào), các phương tiện có mặt trên đường từ trước đó vẫn có thể tham gia giao thông như bình thường.

Bờm xuất phát muộn hơn đoàn ngoại giao ~k~ phút (đoàn ngoại giao xuất hiện ở ~w_1~ tại thời điểm 0, Bờm xuất hiện ở ~s~ tại thời điểm ~k~; Bờm được phép đứng chờ tại các nút giao thông). Hãy xác định thời điểm cậu đến đích sớm nhất có thể.

Dữ liệu

• Dòng 1: hai số nguyên ~n, m~ (~2 \le n \le 10^3~; ~2 \le m \le 10^4~).
• Dòng 2: bốn số nguyên ~s, t, k, c~ (~0 \le k, c \le 10^3~).
• Dòng 3: ~c~ số nguyên ~w_1, w_2, \dots, w_c~.
• ~m~ dòng tiếp theo: mỗi dòng ba số nguyên ~u, v, l~ (~1 \le u \le n~, ~1 \le v \le n~, ~1 \le l \le 10^3~) thể hiện một con đường nối hai nút giao thông ~u, v~ tốn thời gian di chuyển ~l~ phút, không có cặp nút giao thông nào được nối bởi nhiều hơn một con đường.

Kết quả

Một số nguyên là số phút di chuyển tối thiểu (tính từ lúc Bờm xuất phát, bao gồm cả thời gian chờ).

Ví dụ

Ví dụ 1

DISENTR.INP

6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15

DISENTR.OUT

21

Giải thích: Đoàn ngoại giao đi ~5 \to 3 \to 2 \to 4~: đường ~(5,3)~ bị chặn trong khoảng thời gian ~[0, 15)~, đường ~(3,2)~ trong ~[15, 23)~, đường ~(2,4)~ trong ~[23, 26)~ (thời điểm tính từ lúc đoàn xuất hiện). Bờm xuất phát ở nút 1 tại thời điểm 20, đi ~1 \to 2~ đến nơi lúc 22, phải chờ đến 23 mới được vào đường ~(2,3)~, rồi đi tiếp ~3 \to 6~, đến nơi lúc 41, tức là mất 21 phút.

Ví dụ 2

DISENTR.INP

8 9
1 5 5 5
1 2 3 4 5
1 2 8
2 7 4
2 3 10
6 7 40
3 6 5
6 8 3
4 8 4
4 5 5
3 4 23

DISENTR.OUT

40

Giới hạn

• ~2 \le n \le 10^3~, ~2 \le m \le 10^4~.
• ~0 \le k, c \le 10^3~, ~1 \le l \le 10^3~.