Thành phố Festival có ~n~ điểm thăm quan (được đánh số từ ~1, 2, \dots, n~). Các điểm thăm quan này được kết nối bởi ~m~ tuyến đường hai chiều, giữa hai điểm thăm quan có không quá 1 tuyến đường kết nối. Để đi hết mỗi tuyến đường cần tốn một lượng thời gian nhất định, lượng thời gian này không phụ thuộc vào phương tiện giao thông vì thành phố qui định tốc độ di chuyển cố định trên mọi tuyến đường.

Bờm cần di chuyển từ điểm thăm quan ~s~ đến điểm thăm quan ~t~. Tuy nhiên, khi chuẩn bị xuất phát Bờm mới biết do hôm đó là ngày lễ nên có một đoàn diễu hành để quảng bá về du lịch. Để đảm bảo giao thông, một số tuyến đường sẽ bị cấm tạm thời để phục vụ đoàn diễu hành. Hành trình của đoàn diễu hành là ~(x_1, x_2, \dots, x_c)~, hành trình này đảm bảo thông suốt và không có tuyến đường nào xuất hiện quá 1 lần. Đối với một tuyến đường trong hành trình của đoàn diễu hành, tạm kí hiệu là ~(x_i, x_{i+1})~, kể từ khi đoàn diễu hành xuất hiện ở ~x_i~ cho đến khi ra khỏi ~x_{i+1}~, không có phương tiện nào được phép đi vào tuyến đường này (kể cả các phương tiện đó đang ở ~x_i~ hoặc ở ~x_{i+1}~) trừ các phương tiện đang đi trên tuyến đường này (đã rời khỏi ~x_i~, ~x_{i+1}~ và đang đi trên tuyến đường ~(x_i, x_{i+1})~) thì vẫn di chuyển bình thường.

Yêu cầu: hãy xác định tối thiểu sau bao nhiêu phút Bờm đến được điểm thăm quan ~t~. Biết rằng, Bờm xuất phát từ ~s~ muộn hơn đoàn diễu hành ~k~ phút.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~n, m~ (~2 \le n \le 10^3~; ~2 \le m \le 10^4~);
• Dòng thứ hai chứa bốn số nguyên ~s, t, k, c~ (~1 \le s, t \le n~; ~0 \le k, c \le 10^3~);
• Dòng thứ ba chứa ~c~ số nguyên ~x_1, x_2, \dots, x_c~ (~1 \le x_i \le n~; ~i = 1, 2, \dots, c~);
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, l~ (~1 \le u, v \le n~; ~1 \le l \le 10^3~) thể hiện một tuyến đường nối điểm thăm quan ~u~ với điểm thăm quan ~v~, để di chuyển từ ~u~ tới ~v~ cần tốn thời gian là ~l~.

Kết quả

Số phút tối thiểu mà Bờm di chuyển từ điểm thăm quan ~s~ tới điểm thăm quan ~t~.

Ví dụ

FESTIVAL.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

FESTIVAL.OUT

21

Giải thích: Đoàn diễu hành bắt đầu di chuyển thì sau 20 phút Bờm bắt đầu di chuyển từ 1 đến 2. Ở phút thứ 22, Bờm đến 2, đoàn diễu hành đang ở tuyến đường từ 3 đến 2, lúc này Bờm không thể đi từ 2 đến 3 được (vì cấm đường). Bờm phải chờ 1 phút cho đoàn diễu hành về đến 2. Ở phút 23 đường từ 2 đến 3 không bị cấm Bờm di chuyển theo tuyến đường 2 → 3 → 6. Bờm đến 6. Tổng thời gian di chuyển của Bờm là 41 phút. Vì xuất phát muộn 20 phút nên thời gian Bờm di chuyển thực tế là 21 phút.

Giới hạn

• Subtask 1 (30% số test): ~2 \le m \le 1000~.
• Subtask 2 (30% số test): ~1000 < m \le 5000~.
• Subtask 3 (40% số test): ~5000 < m \le 10^4~.